1D DP: Stairs, Coins and Houses

Climbing stairs

Climb 1 or 2 steps at a time; how many ways to reach step n? Your last move came from step i − 1 or i − 2, so ways[i] = ways[i − 1] + ways[i − 2], with ways[0] = ways[1] = 1.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 6;
    vector<long long> ways(n + 1);
    ways[0] = ways[1] = 1;
    for (int i = 2; i <= n; i++) ways[i] = ways[i - 1] + ways[i - 2];
    for (long long w : ways) cout << w << ' ';
    cout << endl;
    return 0;
}

Output

1 1 2 3 5 8 13 

Fewest coins (where greedy fails)

best[a] = fewest coins for amount a. Try each coin as the last one: best[a] = 1 + min(best[a − c]).

#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
using namespace std;

int fewestCoins(const vector<int>& coins, int amount) {
    vector<int> best(amount + 1, INT_MAX);
    best[0] = 0;
    for (int a = 1; a <= amount; a++)
        for (int c : coins)
            if (c <= a && best[a - c] != INT_MAX) best[a] = min(best[a], best[a - c] + 1);
    return best[amount] == INT_MAX ? -1 : best[amount];
}

int main() {
    cout << fewestCoins({1, 3, 4}, 6) << " " << fewestCoins({2}, 3) << endl;
    return 0;
}

Output

2 -1

Don't rob two houses in a row

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> money = {2, 7, 9, 3, 1};
    long long take = 0, skip = 0;     // best if we took / skipped the previous house
    for (int m : money) {
        long long newTake = skip + m;
        skip = max(take, skip);
        take = newTake;
    }
    cout << max(take, skip) << endl;
    return 0;
}

Output

12

Tip: When dp[i] only needs the last one or two values, keep just those variables: O(1) memory.