Reference:

What is DP?

Those who cannot remember the past are condemned to repeat it. — Dynamic Programing
The important fact to observe is that we have attempted to solve a maximization problem involving a particular value of $x$ and a particular value of $N$ by first solving the general problem involving an arbitrary value of $x$ and an arbitrary value of $N$. — R.E. Bellman, 1957

DP is a programming method.

Three Requirements:

  • Optimal Substructure(最优子结构)
    • Can be solved optimally by decomposing it into subproblems adn then recursively find the optimal solutions to the subproblems.
    • You should consider using DP whenever you have to make choices to arrive at the solution, specifically, when the solution relates to subproblems.
  • Overlapping Subproblems(重叠子问题)
    • Subproblems are overlapped such that we can compute only once and store for future use.
    • If subproblems do not overlap -> Divide and Conquer (they both combine the solutions of multiple smaller problems)
  • No-after Effect(无后效性)
    • The optimal solution of a sub-problem will not change when it was used to solve a bigger problem optimally.

Applied to Two Kinds of Problems:

  • Optimization(优化问题)Counting(计数问题)(min、max)

For some problems, DP will not work, e.g. the longest path problem.

Key Steps & Problem Types

Key Steps

  • Find the recurrence(Big problem -> subproblems)
    • The most difficult part.
    • Simple recursive solution incurs high complexity.
      • Has so many overlapped subproblems.
  • Optimization (avoid repeated computation)
    • Top-down (recursion with memoization)
      • Time complexity is clear / 时间复杂度比较清晰
      • Space is usually cannot be optimized / 一般进行不了空间优化
    • Bottom-up
      • Space can be readily optimized.
    • Sometimes, recursion may out-perform a bottom-up DP solution, e.g., when the solution is found early or subproblems can be pruned through bounding.

Problem Types

  • 50%: Sequence / 序列型
    • LIS / 单序列
    • LCS / 双序列(common)
  • 30%: Pascal Triangle / 矩阵坐标型
  • 15%: Knapsack Variants (coin change, subset sum)
  • 5%: Interval or others / 区间型及其他(optimal BST, matrix product, generate binary trees)
    • A bit difficult

Fibonacci Number (1D)

Recurrence: $F(n) = F(n - 1) + F(n - 2)$, where $F(0) = 0$ and $F(1) = 1$.

A function to compute $F(n)$ that recursively invokes itself has a time complexity that is exponential in $n$. This is because the recursive function computes some $F(i)$s repeatedly as shown in the figure below.

The right number is order. Source: EPI p270

1
2
3
4
5
// Recursion O(2^n)
public int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}

Therefore, we can cache intermediate results and make the time complexity for computing the n-th Fibonacci number linear in $n$, but it is at the expense of $O(n)$ storage.

1
2
3
4
5
6
7
8
9
// Top-down O(n)
int[] mem = new int[n + 1]; // Assume init with -1
public int fib(int n) {
if (n <= 1) return n;
if (mem[n] == -1) { // if fib(n) is not in mem
mem[n] = fib(n - 1) + fib(n - 2);
}
return mem[n];
}

Further, minimizing cache space is a recurring theme in DP. In a bottom-up fashion, we can reduce the space complexity of the cache.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Bottom-up O(n) it still needs O(n) space
int[] dp = new int[n + 1];
dp[0] = 0; dp[1] = 1; // init
public int fib(int n) {
if (n <= 1) return 1;
for (int i = 2; i <= n; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}

// We can then easily reduce the space complexity
public int fib(int n) {
if (n <= 1) return n; // f1 f2
int f1 = 0, f2 = 1; // f1, f2, f1+f2
for (int i = 2; i <= n; ++i) {
int temp = f2;
f2 = f1 + f2;
f1 = temp;
}
return f2;
}

Related LC Problems:

Unique Paths (2D)

How many possible unique paths are there?

Explanation: 62. Unique Paths (include obstacle version)

Related LC Problems:

Other Problems

Multiple States: dp[i][0], dp[i][1], dp[i][2]

Increasing Sum / Max / Prefix, Suffix:

Palindromic Problems:

The following contents are not organized!
The following contents are not organized!
The following contents are not organized!

Knapsack

Knapsack 是 NP-Complete 问题。

Note:没有任何贪心算法不能给最优解,比如拿 $\frac{v_i}{w_i}$

No Repetition

Input:

  • v[i] (i=0..n-1): Value
  • w[i] (i=0..n-1): Weight
  • C: Max Weight

Note: Only one copy of each item at most.

Output: Max value sum.

Type: Optimization

问题:

  • 怎么才能递归式地想问题呢?
  • 怎么大问题化小问题?
  • 怎么才是小问题?

**Note:**这里的 i 表示的是第几个,上面的是索引。

f(i, j): 如果只有 1 ~ i 个 item 可以选,并且此时的包重量为 j,你最多能拿走价值多少钱东西?

子问题:f(i-2, j)f(i, j-10)f(i-5, j-15)

选择:

  • take it: f(i-1, j-w[i]) + v[i]
  • leave it: f(i-1, j)
  • 递归式:f(i, j) = max(f(i-1, j-w[i]) + v[i], f(i-1, j))

Recursion:

Note: 以下访问数组 w 和 v 时 i 都要减去 1。

1
2
3
4
5
6
7
8
9
10
// O(2^n)
public int ks(int[] v, int[] w, i, j) {
if (i == 0 || j == 0) return 0;
int best = ks(v, w, i - 1, j); // leave it
if (j >= w[i - 1]) { // take it
int val = ks(v, w, i - 1, j - w[i - 1]) + v[i - 1];
best = Math.max(best, val);
}
return best;
}

Top-down:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// dp lookup
int[][] dp = new int[n + 1][C + 1]; // and init with -1
// O(Cn)
public int ks_td(int[] v, int[] w, i, j) {
if (i == 0 || j == 0) return 0;
if (dp[i][j] != -1) return dp[i][j]; // new
int best = ks(v, w, i - 1, j); // leave it
if (j >= w[i - 1]) { // take it
int val = ks(v, w, i - 1, j - w[i - 1]) + v[i - 1])
best = Math.max(best, val);
}
dp[i][j] = best; // new
return best;
}

Bottom-up:

f(i, j) = max(f(i - 1, j), f(i - 1, j - w[i - 1]) + v[i - 1])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// O(Cn)
int ks_bu(int[] v, int[] w, C) {
int n = v.length;
int[][] dp = new int[n + 1][C + 1];
// base case
for (int j = 0; j <= C; ++j) dp[0][j] = 0;
for (int i = 0; i <= n; ++i) dp[i][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= C; ++j) {
int best = dp[i - 1][j];
if (j >= w[i - 1]) {
int val = dp[i - 1][j - w[i - 1]] + v[i - 1];
best = Math.max(best, val);
}
dp[i][j] = best;
}
}
return dp[n][C];
}

Repetition

Input:

  • v[i] (i=0..n-1): Value
  • w[i] (i=0..n-1): Weight
  • C: Max Weight

Note: Infinite copies of each item at most.

Output: Max value sum.

Type: Optimization

关键点:拿东西后这个东西还在,只是包的可用重量变小了。

Idea: f(i) 是当包的大小为i时,最多能拿走价值多少钱的东西。

递归式:f(i) = $\max_{k=1\ldots n}$(f(i - w[k]) + v[k])

Recursion:

1
2
3
4
5
6
7
8
9
10
int ks(int[] v, int[] w, i) {
if (i == 0) return 0;
int best = Integer.MIN_VALUE;
for (int k = 0; k < v.length; ++k) {
if (i >= w[k]) { // can take
best = Math.max(best, ks(v, w, i - w[k]) + v[k]);
}
}
return best;
}

Top-down:

1
2
3
4
5
6
7
8
9
10
11
12
int[] dp = new int[](n + 1); // and init with -1
int ks_td(int[] v, int[] w, i) {
if (i == 0) return 0;
if (dp[i] != -1) return dp[i];
for (int k = 0; k < v.length; ++k) {
if (i >= w[k]) { // can take
dp[i] = Math.max(dp[i], ks_td(v, w, C - w[k]) + v[k]);
}
}
// dp[C] = best; // not necessary.
return dp[i];
}

Bottom-up:

递归式:f(i) = $\max_{k=1\ldots n}$(f(i - w[k]) + v[k])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int ks_bu(int[] v, int[] w, int C) {
int[] dp = new int[C + 1];
for (int i = 0; i < C + 1; ++i) dp[i] = -1;

for (int i = 1; i <= C; ++i) {
for (int k = 0; k < v.length; ++k) {
if (i >= w[k]) { // can take
// all values stored in dp[i] for comparison
int val = dp[i - w[k]] + v[k];
dp[i] = Math.max(dp[i], val);
}
}
}
return dp[C];
}

Variants

有一个国家发现了 5 座金矿,每座金矿的黄金储量不同,需要参与挖掘的工人数也不同。参与挖矿工人的总数是 10 人。每座金矿要么全挖,要么不挖,不能派出一半人挖取一半金矿。要求用程序求解出,要想得到尽可能多的黄金,应该选择挖取哪几座金矿?

332. Coin Change

Bottom-up:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
for (int i = 0; i <= amount; ++i) dp[i] = -1;
for (int coin : coins) {
if (coin <= amount) dp[coin] = 1;
}
for (int i = 1; i <= amount; ++i) {
for (int coin : coins) {
if (coin > i) continue;
if (dp[i - coin] == -1) continue;
if (dp[i] == -1 || dp[i - coin] + 1 < dp[i]) {
dp[i] = dp[i - coin] + 1;
}
}
}
return dp[amount];
}

你好,我是分界线

Two methods:

  • Top-down (Memo) => Extra memory
  • Bottom-up => Better

Key steps:

  • Recursion
  • Store (Memoize intermediate results)
  • Bottom-up (optional)

钢条切割

对于 $r_n(n \geq 1)$,我们可以用更短的钢条的最优切割收益来描述:

$$r_n = \max(p_n, r_1 + r_{n-1}, r_2 + r_{n-2}, \ldots, r_{n-1} + r_1)$$

For example, when $n = 3$ we have as follows:

$$r_3 = \max(p_3, r_1 + r_2, r_2 + r_1)$$

第一个参数 $p_n$ 对应不切割,直接求出长度为 $n$ 的方案,其他 $n-1$ 个参数对应了 $n-1$ 种切割方案。

关于子问题的最优解,并在所有可能的两端切割方案重选取组合收益最大者,构成原问题的最优解。我们称钢条切割问题满足最优子结构(optimal substructure)性质:

  • 问题的最优解由相关子问题的最优解组合而成,而这些子问题可以独立求解。

钢条切割问题还存在一种相似的但更为简单但递归求解方法:我们将钢条从左边切割下长度为 $i$ 的一段,只对右边剩下的长度为 $n-i$ 的一段继续进行切割(递归求解),对左边一段不再进行切割。因此,上面的公司可以简化为:

$$r_n = \max_{1 \leq i \leq n}(p_i + r_{n-i})$$

For example, when $n = 3$ we have as follows:

$$r_3 = \max_{1 \leq i \leq 3}(p_1 + r_2, p_2 + r_1, p_3 + r_0)$$

1
2
3
   0  1  2  3  4  5  6  7  8  9 
L: 1 2 3 4 5 6 7 8 9 10
p: 1 5 8 9 10 17 17 20 24 30

Recursive version:

1
2
3
4
5
6
7
8
9
10
11
12
public static int cut(int[] p, int n) { // n is the length
if (n == 0) return 0;
int q = Integer.MIN_VALUE;
for (int i = 1; i <= n; ++i) {
// 1st: p1 + r(n-1) => p[0] + r(n-1)
// 2nd: p2 + r(n-2) => p[1] + r(n-2)
// ...
// nnd: pn + r(0) => p[n-1] + r(0)
q = Math.max(q, p[i - 1] + cut(p, n - i));
}
return q;
}

Memo version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static int cutMemo(int[] p) {
int[] memo = new int[p.length + 1];
for (int i = 0; i < p.length; ++i) {
memo[i] = -1;
}
return cut(p, p.length, memo);
}

public static int cut(int[] p, int n, int[] memo) {
int q = Integer.MIN_VALUE;
if (memo[n] >= 0) q = memo[n];
else if (n == 0) q = 0;
else {
for (int i = 1; i <= n; ++i) {
q = Math.max(q, p[i - 1] + cut(p, n - i, memo));
}
}
r[n] = q;
return q;
}

这道钢条切割问题的经典之处在于自底向上的动态规划问题的处理,理解了这个也就理解了动态规划的精髓。

Bottom-up dp version:

1
2
3
4
5
6
7
8
9
10
public static int bottom_up_cut(int[] p) {
int[] memo = new int[p.length + 1]; // extra for 0, r(i) = r[i]
for (int i = 1; i <= p.length; ++i) {
int q = Integer.MIN_VALUE;
for (int j = 1; j <= i; ++j) {
q = Math.max(q, p[j - 1] + memo[i - j]);
}
memo[i] = q;
}
}

0-1 Knapsack

Naive Recursive Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int[] v;
int[] w;
public int ks(int C) {
return ks(v.length - 1, C);
}
private int ks(int n, int C) {
if (n < 0 || C <= 0) {
result = 0;
} else if (w[n] > C) { // too heavy
result = ks(n - 1, C);
} else {
int tmp1 = ks(n - 1, C); // no
int tmp2 = v[n] + ks(n - 1, C - w[n]); // yes
result = max(tmp1, tmp2);
}
return result;
}

Comment