Dynamic programming is a technique for solving problems recursively, with overlapping sub-problems. This approach works only when the solution to sub-problems share the same structure with the final solution. If the prerequisite is satisfied, the conceptual way of solving the problem is to derive the recursion, and builds up the result bottoms-up. Some examples are listed below.

§Knapsack

Problem spec:

Given a set of items, each of which is associated with some weight and value. Find the subset of items which can be carried into the knapsack with weight limit W. It is required that the cumulative value of the items in the knapsack is maximum value possible.

Sample:

1
2
3
4
values = {10, 40, 30, 50};
weights = {5, 4, 6, 3};
W = 10
result = 40 + 50 = 90

For analyzing the problem, let’s focus on the last recursion step, i.e. deciding if last item (weight: 3, value: 50) should be selected. In this case, we only have two options, select it or drop it, corresponding to max value obtained from selecting from the first three items with weight constraint 7, and selecting from the first three items with weight constraint 10.

1
2
m[i][j] = max value obtained from selecting up to i-th items with weight contraint j
m[i][j] = max(m[i-1][j-w_i], m[i-1][j] + v_i)

The complete Java code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Main {

  static int knapsack(int W, int[] values, int[] weights) {
    assert values.length == weights.length;

    // m[i][j] max value up to item i with j weight constraint
    int[][] m = new int[weights.length + 1][W + 1];

    for (int i = 1; i <= weights.length; ++i) {
      for (int j = 1; j <= W; ++j) {
        if (weights[i - 1] > j) {
          m[i][j] = m[i - 1][j];
        } else {
          m[i][j] = Math.max(
                  m[i - 1][j],
                  m[i - 1][j - weights[i - 1]] + values[i - 1]
          );
        }
      }
    }

    return m[weights.length][W];
  }

  static void test0() {
    int[] values = {10, 40, 30, 50};
    int[] weights = {5, 4, 6, 3};
    int ret = knapsack(10, values, weights);
    assert ret == 90;
    System.out.println("Result : " + ret);
  }

  static void test1() {
    int[] values = {1, 2, 5, 9, 4};
    int[] weights = {2, 3, 3, 4, 6};
    int ret = knapsack(10, values, weights);
    assert ret == 16;
    System.out.println("Result : " + ret);
  }

  public static void main(String[] args) {
    test0();
    test1();
  }
}

§Hop

Given an array of non-negative integers and a pointer pointing at the zeroth slot of the array. The pointer can only incremented by 4 or 7, and such process repeats until it goes beyond the bound of the array. Devise a moving strategy so that the sum of all slots the pointer pointed reaches the maximum. Your solution should calculate this maximum.

Sample:

1
2
3
4
5
6
7
array = {1, 2, 3, 4, 5}
result = [0, 4]
sum = array[0] + array[4] = 6

array = {1, 2, 0, 4, 5, 3, 9, 8}
result = [0, 7]
sum = array[0] + array[7] = 9

The complete Java code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
import java.util.*;

class Main {

  private static List<LinkedList<Integer>> loop(int max,
      List<LinkedList<Integer>> traces) {
    boolean use_new = false;

    List<LinkedList<Integer>> new_traces = new ArrayList<>();

    for (int i = 0; i < traces.size(); ++i) {
      LinkedList<Integer> t = traces.get(i);
      if (t.getLast() + 4 < max) {
        use_new = true;
        if (t.getLast() + 7 < max) {
          LinkedList<Integer> t1 = (LinkedList<Integer>) t.clone();
          t1.add(t.getLast() + 7);
          new_traces.add(t1);
        }
        t.add(t.getLast() + 4);
      }
      new_traces.add(t);
    }

    if (use_new) return loop(max, new_traces);

    return traces;
  }

  static int hop_force(int[] array) {
    assert array.length > 0;

    List<LinkedList<Integer>> traces = loop(array.length,
            new ArrayList<LinkedList<Integer>>(Collections.singletonList(
                    new LinkedList<>(Collections.singletonList(0)))));

    int[] sums = new int[traces.size()];

    for (int i = 0; i < traces.size(); ++i) {
      LinkedList<Integer> t = traces.get(i);
      for (Integer index : t) {
        assert index >= 0 && index < array.length;
        sums[i] += array[index];
      }
    }

    return Arrays.stream(sums).max().getAsInt();
  }

  private static boolean is_valid(int[] cost, int index) {
    return index >= 0 && cost[index] >= 0;
  }

  private static int last_max(int[] cost) {
    if (cost.length <= 4) return cost[0];

    int[] last4 = Arrays.copyOfRange(cost, cost.length - 4, cost.length);
    return Arrays.stream(last4).max().getAsInt();
  }

  static int hop(int[] array) {
    assert array.length > 0;
    int[] cost = new int[array.length];

    cost[0] = array[0];
    boolean left, right;

    for (int i = 1; i < array.length; ++i) {
      left = is_valid(cost, i - 4);
      right = is_valid(cost, i - 7);
      if (!left && !right) {
        cost[i] = -1;
        continue;
      }
      if (left && right) {
        cost[i] = array[i] + Math.max(cost[i - 4], cost[i - 7]);
        continue;
      }

      if (left) {
        cost[i] = array[i] + cost[i - 4];
      } else {
        cost[i] = array[i] + cost[i - 7];
      }
    }

    return last_max(cost);
  }

  private static void eq(int x, int y) {
    if (x != y) {
      System.exit(-1);
    }
  }

  static void rand_test(int size) {
    Random rand = new Random();
    int[] array = new int[size];
    for (int i = 0; i < size; ++i) {
      array[i] = rand.nextInt(100);
    }

    int mine = hop(array);
    int correct = hop_force(array);

    eq(mine, correct);
    System.out.println("Result : " + mine);
  }

  static void test0() {
    int[] array = {1, 2, 3, 4, 5};
    int mine = hop(array);
    int correct = hop_force(array);

    eq(mine, correct);
    System.out.println("Result : " + mine);
  }

  static void test1() {
    int[] array = {1, 2, 0, 4, 5, 3, 9, 8};
    int mine = hop(array);
    int correct = hop_force(array);

    eq(mine, correct);
    System.out.println("Result : " + mine);
  }

  public static void main(String[] args) {
    // test0();
    // test1();
    rand_test(120);
    System.out.println("Done");
  }
}

§Counting change

How many different ways can we make change of $1.00, given half-dollars, quarters, dimes, nickels, and pennies? More generally, can we write a procedure to compute the number of ways to change any given amount of money?

The scheme code from http://xuanji.appspot.com/isicp/1-2-procedures.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(define (count-change amount)
  (cc amount 5))
(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount
                     (- kinds-of-coins 1))
                 (cc (- amount
                        (first-denomination kinds-of-coins))
                     kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))

My solution using DP in Java. dp[i][j] means that using coins up to coin_kinds[j], how many ways there are for exchanging i amount of money.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Main {
    static int count_coin(int amount) {
        int[] coins = {1, 5, 10, 25, 50};
        int coin_kinds = coins.length;

        int[][] dp = new int[amount + 1][coin_kinds];

        for (var j=0; j<coin_kinds; ++j) {
            dp[0][j] = 1;
        }

        for (var i=1; i<amount+1; ++i) {
            dp[i][0] = 1;
        }

        for (var i=1; i<amount+1; ++i) {
            for (var j=1; j<coin_kinds; ++j) {
                var coin_value = coins[j];
                if (i < coin_value) {
                    dp[i][j] = dp[i][j-1];
                } else {
                    dp[i][j] = dp[i - coin_value][j] + dp[i][j - 1];
                }
            }
        }

        return dp[amount][coin_kinds-1];
    }

    public static void main(String[] args) {
        System.out.println(count_coin(100)); // 292
    }
}