Dynamic Programming Notes 👀

Reference:

算法-动态规划 Dynamic Programming–从菜鸟到老鸟
五大常用算法之二：动态规划算法
Huahua Dynamic Programming (videos)
Elements of Programming Interviews in Java, Dynamic Programming

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

// 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.

// 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.

// 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;
}

Unique Paths (2D)

How many possible unique paths are there?

Explanation: 62. Unique Paths (include obstacle version)

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。

// 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:

// 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])

// 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:

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:

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])

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:

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:

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:

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:

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:

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;
}

forkercat.blog

What is DP?

Key Steps & Problem Types

Key Steps

Problem Types

Fibonacci Number (1D)

Unique Paths (2D)

Other Problems

Knapsack

No Repetition

Repetition

Variants

332. Coin Change

你好，我是分界线

钢条切割

0-1 Knapsack