Dynamic Programming

Dynamic Programming

由大化小, 小问题存在交集, 解决重复计算

DP 的实现方式

1. 记忆化搜索 (递归)

2. 循环

   1. 自顶向下

   2. 自底向上

如何想到需要用 DP 来解题?

1. one of the following three indicators in problem description

   1. max / min

   2. yes / no (能否 ....)

   3. count(*)

2. 原数组/序列不能排序, 交换位置 (不允许改变)

DP 四个要素

1. 状态 State

   1. f[][] 表示 ....

2. 方程 Function

   1. 研究如何从上一步走到下一步

3. 初始化 Initialization

   1. 对那几个点进行初始化

4. 答案 Answer

   1. 答案在哪里? f[n]? f[0]?

整理的 4 种 典型 DP

1. Matrix DP

2. Sequence DP

3. Two Sequences DP

4. Backpack DP

Matrix DP

1. 状态 State

   1. f[x][y] 表示从起点走到坐标 (x, y) 的 .....

2. 方程 Function

   1. 研究走到 (x, y) 这个点之前的一步

3. 初始化 Initialization

   1. 对那几个点进行初始化? 边界? 顶点

4. 答案 Answer

   1. 答案在哪里? f[n]? f[0]?

例题

• Minimum Path Sum

• Unique Path Sum I

• Unique Path Sum II

解析

pass

Sequence DP

1. State: f[i] 表示"前i"个位置/数字/字母, (以第i个为).....

2. Function: f[i] = f[j] .... j < i

3. Initialization: f[0] ....

4. Answer: f[n - 1] ...

例题

• Climbing Stairs

• Jump Game

• Palindrome Partitioning II

• Word Break

• Longest Increasing Subsequence

解析

pass

Two Sequence DP

1. State: f[i][j] 代表第一 sequence 的前 i 个数字/字符, 配上第二个 sequence 的前 j 个数字/字符, .....

2. Function: f[i][j] 研究 第 i 个和第 j 个的匹配关系

3. Initialization: f[i][0] 和 f[0][i]

4. Answer: f[s1.length()][s2.length()]

例题

• Longest Common Subsequence

• Longest Common Substring

• Edit Distance

• Distinct Subsequences

• Interleaving String

解析

pass

Backpack

n 个整数 a[1, ..., n], 装满 m 的背包

1. State: f[i][j] "前 i" 个数, 能否组成和为 j

2. Function: f[i][j] = f[i -1][j - a[j]] or f[i - 1][j]

3. Initialization: f[x][0] = True, f[0][1, ...., m] = False

4. Answer: 使得 f[n][x] 最大的 (0 <= x <= m)

例题

• Backpack

• Backpack II

• K Sum

• Minimum Adjustment Cost

解析

pass