1D DP: Coins and Robbers

Fewest coins (where greedy failed)

Coins 1, 3 and 4, amount 6. Greedy said 3 coins; the truth is 2. DP gets it right.

• dp[a] = the fewest coins that make amount a.
• Base case: dp[0] = 0.
• Rule: for each coin c ≤ a, we could use c last, so dp[a] = min(dp[a - c] + 1).

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] coins = {1, 3, 4};
        int amount = 6;
        int INF = Integer.MAX_VALUE / 2;          // "impossible" (halved so +1 can't overflow)
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, INF);
        dp[0] = 0;
        for (int a = 1; a <= amount; a++) {
            for (int c : coins) {
                if (c <= a && dp[a - c] + 1 < dp[a]) dp[a] = dp[a - c] + 1;
            }
        }
        System.out.println(Arrays.toString(dp));
        System.out.println("fewest coins for " + amount + ": " + dp[amount]);
    }
}

Output

[0, 1, 2, 1, 1, 2, 2]
fewest coins for 6: 2

The careful burglar

Houses in a row hold some money. Taking from two neighbouring houses sets off the alarm. What's the most you can take?

• best[i] = the most money from the first i + 1 houses.
• Rule: either skip house i (best[i - 1]) or take it plus the best from two houses back (money[i] + best[i - 2]). Pick the bigger.

public class Main {
    public static void main(String[] args) {
        int[] money = {6, 7, 1, 30, 8, 2, 4};
        int n = money.length;
        int[] best = new int[n];
        best[0] = money[0];
        best[1] = Math.max(money[0], money[1]);
        for (int i = 2; i < n; i++) {
            best[i] = Math.max(best[i - 1], money[i] + best[i - 2]);
        }
        System.out.println(java.util.Arrays.toString(best));
        System.out.println("most money: " + best[n - 1]);
    }
}

Output

[6, 7, 7, 37, 37, 39, 41]
most money: 41

Tip: Both tables only look back a few steps. You could keep just two or three variables instead of the whole array – but write the array version first; it's much easier to get right.