intro-dp-exmp1-bu.cpp

int ans[MAX_N];
ans[0] = 0; // base case

for (int i = 1; i <= n; ++i) {
    ans[i] = 1e9; // don't know a way to solve yet
    if (i-1 >= 0) // try using 1-baht coin if possible
        ans[i] = min(ans[i], 1+ans[i-1]);
    if (i-3 >= 0) // try using 3-baht coin if possible
        ans[i] = min(ans[i], 1+ans[i-3]);
    if (i-4 >= 0) // try using 4-baht coin if possible
        ans[i] = min(ans[i], 1+ans[i-4]);
}

cout << change(n) << endl;
// if n = 6, result = 2