Reconstructing solutions

1// returns the steps stood on, in order, for the cheapest climb; position n is the top
2static List<Integer> cheapestSteps(int[] cost) {
3    int n = cost.length;
4    int[] dp = new int[n + 1], parent = new int[n + 1];
5    for (int i = 2; i <= n; i++) {
6        int fromOne = dp[i - 1] + cost[i - 1], fromTwo = dp[i - 2] + cost[i - 2];
7        if (fromOne <= fromTwo) { dp[i] = fromOne; parent[i] = i - 1; }     // remember where the best value came from
8        else { dp[i] = fromTwo; parent[i] = i - 2; }
9    }
10    LinkedList<Integer> steps = new LinkedList<>();
11    for (int at = parent[n]; ; at = parent[at]) {            // follow the pointers back from the top
12        steps.addFirst(at);
13        if (at <= 1) break;
14    }
15    return steps;
16}

1// returns the 1-based indices of the chosen items
2static List<Integer> chosenItems(int[][] items, int capacity) {
3    int n = items.length;
4    int[][] dp = new int[n + 1][capacity + 1];
5    boolean[][] took = new boolean[n + 1][capacity + 1];     // the choice made in each cell
6    for (int i = 1; i <= n; i++) {
7        for (int w = 0; w <= capacity; w++) {
8            dp[i][w] = dp[i - 1][w];
9            if (items[i - 1][0] <= w && dp[i - 1][w - items[i - 1][0]] + items[i - 1][1] > dp[i][w]) {
10                dp[i][w] = dp[i - 1][w - items[i - 1][0]] + items[i - 1][1];
11                took[i][w] = true;
12            }
13        }
14    }
15    LinkedList<Integer> chosen = new LinkedList<>();
16    for (int i = n, w = capacity; i >= 1; i--) {
17        if (took[i][w]) { chosen.addFirst(i); w -= items[i - 1][0]; }
18    }
19    return chosen;
20}

1// best[i] from the earlier lesson: best loot from the first i houses; returns the robbed houses (1-based)
2static List<Integer> robbedHouses(int[] value) {
3    int n = value.length;
4    int[] best = new int[n + 1];
5    for (int i = 1; i <= n; i++) best[i] = Math.max(best[i - 1], (i >= 2 ? best[i - 2] : 0) + value[i - 1]);
6    LinkedList<Integer> houses = new LinkedList<>();
7    int i = n;
8    while (i >= 1) {
9        if (best[i] == best[i - 1]) i--;                     // skipped: the value did not change
10        else { houses.addFirst(i); i -= 2; }                 // robbed: jump over the neighbour
11    }
12    return houses;
13}

1// number of combinations (order does not matter): coins outer, amounts inner
2static long countCombinations(int[] coins, int amount) {
3    long[] ways = new long[amount + 1];
4    ways[0] = 1;
5    for (int c : coins) for (int a = c; a <= amount; a++) ways[a] += ways[a - c];
6    return ways[amount];
7}
8
9// number of ordered sequences: amounts outer, coins inner
10static long countSequences(int[] coins, int amount) {
11    long[] ways = new long[amount + 1];
12    ways[0] = 1;
13    for (int a = 1; a <= amount; a++) for (int c : coins) if (c <= a) ways[a] += ways[a - c];
14    return ways[amount];
15}

1// all coin multisets with the fewest coins, each listed in non-decreasing order; coins must be sorted ascending
2static List<List<Integer>> optimalCombinations(int[] coins, int amount) {
3    int[] dp = new int[amount + 1];
4    Arrays.fill(dp, Integer.MAX_VALUE);
5    dp[0] = 0;
6    for (int a = 1; a <= amount; a++)
7        for (int c : coins) if (c <= a && dp[a - c] != Integer.MAX_VALUE) dp[a] = Math.min(dp[a], dp[a - c] + 1);
8    List<List<Integer>> out = new ArrayList<>();
9    if (dp[amount] != Integer.MAX_VALUE) collect(coins, dp, amount, coins.length - 1, new ArrayDeque<>(), out);
10    return out;
11}
12
13// walk the table from 'remaining' down to 0, choosing coins in non-increasing order to avoid duplicates
14static void collect(int[] coins, int[] dp, int remaining, int maxIndex, Deque<Integer> path, List<List<Integer>> out) {
15    if (remaining == 0) { out.add(new ArrayList<>(path)); return; }
16    for (int i = maxIndex; i >= 0; i--) {
17        int c = coins[i];
18        if (c <= remaining && dp[remaining - c] == dp[remaining] - 1) {     // this coin lies on some optimal solution
19            path.addFirst(c);
20            collect(coins, dp, remaining - c, i, path, out);
21            path.removeFirst();
22        }
23    }
24}