intro-dp-exmp1-td.cpp

int memo[MAX_N]; // initially set all to -1 to mark as "not done yet"

int change(int i) {
    // base cases:
    if (i == 0) return 0;
    if (i < 0) return 1e9; // 1e9 = 1,000,000,000
    // already solved cases:
    if (memo[i] != -1)
        return memo[i];
    
    // recursive step:
    int ans = 1 + min(change(i-1), min(change(i-3), change(i-4)));
    memo[i] = ans; // memoize the answer
    return ans;
}

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