# Dynamic Programming Notes 👀

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

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

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], dp[i], dp[i]

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，你最多能拿走价值多少钱东西？

• 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。

Top-down:

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

### 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时，最多能拿走价值多少钱的东西。

Recursion:

Top-down:

Bottom-up: Bottom-up:

## 你好，我是分界线

Two methods:

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

Key steps:

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

## 钢条切割  $$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)$$

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

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

Recursive version:

Memo version:

Bottom-up dp version:

## 0-1 Knapsack

Naive Recursive Solution: Comment Junhao Wang
a software engineering cat