Canonical beginner DP

**State:** ways[i] is the number of ways to reach step i. **Transition:** the last move was a 1-step from i - 1 or a 2-step from i - 2, so ways[i] = ways[i - 1] + ways[i - 2]. **Base:** ways[0] = ways[1] = 1. **Answer:** ways[n]. The “n = 7” presets give 21, and “n = 12” gives 233.

The count for n = 45 is 1 836 311 903, which still fits in int, but n = 46 gives 2 971 215 073, which does not; long lasts much longer, so for large n use long or BigInteger, or return the result modulo a given number.

1static long climbStairs(int n) {
2    long a = 1, b = 1;                           // ways to reach steps i - 1 and i
3    for (int i = 2; i <= n; i++) { long c = a + b; a = b; b = c; }
4    return b;
5}

1static long ways(int n) {                         // dp[i] = number of ways to reach step i with moves of 1 or 2
2    long[] dp = new long[n + 1]; dp[0] = 1;       // one way to stand at the start: do nothing
3    if (n >= 1) dp[1] = 1;
4    for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];   // arrive from i-1 or from i-2
5    return dp[n];
6}
7static long waysRolling(int n) {
8    long prev2 = 1, prev1 = 1;                    // dp[0], dp[1]
9    for (int i = 2; i <= n; i++) { long cur = prev1 + prev2; prev2 = prev1; prev1 = cur; }   // forget what is no longer needed
10    return prev1;
11}

Fibonacci is climbing stairs with different base cases: F(0) = 0, F(1) = 1, and F(n) = F(n - 1) + F(n - 2). The naive recursion takes exponential time; memoization or a loop takes O(n). The animation shows the memoised version computing F(10) = 55 in 19 calls instead of 177.

long holds F(92) = 7 540 113 804 746 346 429 but overflows at F(93); for larger indices use BigInteger, or fast doubling for O(log n) multiplications. Prefer the loop to recursion for any value of n that is not tiny.

1static long fibIterative(int n) {
2    long a = 0, b = 1;                           // F(i) and F(i + 1)
3    for (int i = 0; i < n; i++) { long c = a + b; a = b; b = c; }
4    return a;
5}
6
7static java.math.BigInteger fibBig(int n) {
8    java.math.BigInteger a = java.math.BigInteger.ZERO, b = java.math.BigInteger.ONE;
9    for (int i = 0; i < n; i++) { java.math.BigInteger c = a.add(b); a = b; b = c; }
10    return a;
11}

1static long[] memo = new long[100];
2static long fib(int n) {
3    if (n <= 1) return n;                       // base cases
4    if (memo[n] != 0) return memo[n];           // already solved: reuse it
5    return memo[n] = fib(n - 1) + fib(n - 2);   // solve once, remember
6}

A street of houses has loot value[i], and robbing two adjacent houses triggers an alarm. **State:** best[i] is the most loot from the first i houses. **Transition:** skip house i, or rob it and skip its neighbour: best[i] = max(best[i - 1], best[i - 2] + value[i]). **Base:** best[0] = 0.

On the “Classic” preset (2, 7, 9, 3, 1) the answer is 12 from houses 1, 3 and 5 (2 + 9 + 1). “One big house” (1, 2, 50, 1, 1) is 52 from houses 1, 3 and 5 too: the 50 is worth more than anything around it. The take-or-skip pattern recurs everywhere: subsets, knapsack and scheduling.

1static int robO1(int[] value) {
2    int skip = 0, take = 0;                      // best total ending with the current house skipped / robbed
3    for (int v : value) {
4        int newTake = skip + v;
5        skip = Math.max(skip, take);
6        take = newTake;
7    }
8    return Math.max(skip, take);
9}

1static int rob(int[] a) {                             // no two adjacent houses
2    int n = a.length; int[] dp = new int[n + 1];      // dp[i] = best loot from the first i houses
3    dp[1] = a[0];
4    for (int i = 2; i <= n; i++)
5        dp[i] = Math.max(dp[i - 1], dp[i - 2] + a[i - 1]);   // skip house i, or rob it and use the best before the neighbour
6    return dp[n];
7}

Each step has a cost, paid when you step off it; you may start at step 0 or 1 and move 1 or 2 steps at a time; find the cheapest way to get past the last step. **State:** dp[i] is the cheapest cost to stand on position i (position n is the top). **Transition:** dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]). **Base:** dp[0] = dp[1] = 0, because starting is free.

The “Mixed costs” preset for 10, 15, 20, 5, 30, 8 costs 28 by standing on steps 1, 3 and 5 (15 + 5 + 8). “Skip the expensive steps” uses 1, 100, 1, 1, 1, 100, 1, 1, 100, 1 and costs 6, avoiding every 100. Notice how it differs from house robber: both choose among two predecessors, but here every path must reach the end.

1static int minCostO1(int[] cost) {
2    int a = 0, b = 0;                            // dp[i - 2] and dp[i - 1]
3    for (int i = 2; i <= cost.length; i++) {
4        int c = Math.min(b + cost[i - 1], a + cost[i - 2]);
5        a = b;
6        b = c;
7    }
8    return b;
9}

1static int minCost(int[] cost) {                 // you may start on step 0 or 1 and pay cost[i] when you leave step i
2    int n = cost.length; int[] dp = new int[n];  // dp[i] = cheapest total to stand on step i, including cost[i]
3    dp[0] = cost[0]; dp[1] = cost[1];
4    for (int i = 2; i < n; i++) dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);   // best predecessor, then pay for this step
5    return Math.min(dp[n - 1], dp[n - 2]);        // the top is one step past the end, reached from either of the last two
6}

A string of digits is decoded by letters A = 1 to Z = 26. Count the ways. **State:** dp[i] is the number of ways to decode the first i characters. **Transition:** add dp[i - 1] if the last digit is 1 to 9, and add dp[i - 2] if the last two digits form a number from 10 to 26. **Base:** dp[0] = 1.

“226” has 3 ways (2-2-6, 22-6 and 2-26), “11106” has 2, “2101” has 1 and “06” has 0. This is a **counting** DP: the transition adds instead of taking a minimum or maximum, and the same table shape then handles both.

1static int numDecodingsO1(String s) {
2    int prev2 = 0, prev1 = 1;                    // dp[i - 2] and dp[i - 1], starting at i = 1 (dp[0] = 1)
3    for (int i = 1; i <= s.length(); i++) {
4        int cur = 0;
5        if (s.charAt(i - 1) != '0') cur += prev1;
6        if (i >= 2) {
7            int two = (s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0');
8            if (two >= 10 && two <= 26) cur += prev2;
9        }
10        prev2 = prev1;
11        prev1 = cur;
12    }
13    return prev1;
14}

1static int numDecodings(String s) {                  // 'A'=1 ... 'Z'=26
2    int n = s.length(); int[] dp = new int[n + 1];     // dp[i] = ways to decode the first i digits
3    dp[0] = 1;                                         // the empty prefix has one decoding
4    for (int i = 1; i <= n; i++) {
5        if (s.charAt(i - 1) != '0') dp[i] += dp[i - 1];                            // last digit alone (1-9)
6        if (i >= 2 && s.charAt(i - 2) != '0' && Integer.parseInt(s.substring(i - 2, i)) <= 26) dp[i] += dp[i - 2];   // last two digits (10-26)
7    }
8    return dp[n];
9}

Fewest coins that sum to an amount, with unlimited coins. **State:** dp[a] is the fewest coins for amount a. **Transition:** dp[a] = 1 + min(dp[a - c]) over coins c <= a. **Base:** dp[0] = 0. Use a value larger than any real answer (amount + 1) for 'impossible', and return -1 at the end if dp[amount] is still that value.

On coins 1, 3, 4 and amount 6 the table ends at 2, with the coins 3 + 3, where greedy took three. “Impossible amount” (coins 5, 10, amount 7) leaves dp[7] untouched and returns -1. The same table shape counts combinations instead if you add rather than minimise, as the counting lesson later in this chapter shows.

1static int coinChange(int[] coins, int amount) {
2    int[] dp = new int[amount + 1];
3    Arrays.fill(dp, amount + 1);                 // amount + 1 is larger than any real answer: 'impossible'
4    dp[0] = 0;
5    for (int a = 1; a <= amount; a++) {
6        for (int c : coins) {
7            if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
8        }
9    }
10    return dp[amount] > amount ? -1 : dp[amount];
11}

1static int minCoins(int[] coins, int amount) {
2    int INF = amount + 1;
3    int[] dp = new int[amount + 1]; Arrays.fill(dp, INF); dp[0] = 0;             // dp[a] = fewest coins that make a
4    for (int a = 1; a <= amount; a++)
5        for (int c : coins)
6            if (c <= a && dp[a - c] + 1 < dp[a]) dp[a] = dp[a - c] + 1;          // one coin c, then solve a - c
7    return dp[amount] >= INF ? -1 : dp[amount];
8}
9static long ways(int[] coins, int amount) {
10    long[] dp = new long[amount + 1]; dp[0] = 1;                                 // one way to make 0: take nothing
11    for (int c : coins)                                                          // coins in the outer loop: each combination is counted once
12        for (int a = c; a <= amount; a++) dp[a] += dp[a - c];
13    return dp[amount];
14}