警告
本文最后更新于 2022-08-14，文中内容可能已过时。
Dynamic Programming
定义：
步骤：
- 确定「初始条件」
- 确定「状态」
- 确定「可选择列表」
- 确定「状态转移方程」
- 数组优化时间
- 降维优化空间
思路：
1
2
| def fib(n):
return fib(n - 1) + fib(n - 2)
|
1
2
3
4
| def fib(n):
for i in range(n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
|
Longest Increasing Subsequence
$$
dp[i]=s[0:i]的最长上升子序列长度
$$
$$
dp[0] = 0
$$
$$
dp[i]=\max(dp[i],dp[j] + 1) \quad \text{if } j \lt i \text{ and } s_j \lt s_i
$$
Longest Common Subsequence
$$
dp[i][j]=x[0:i]和y[0:j]的最长公共子序列长度
$$
$$
dp[i][0] = dp[0][j] = 0
$$
$$
dp[i+1][j+1]=
\begin{aligned}
\begin{cases}
dp[i][j] + 1& \text{if } x_i = y_j \newline
\max(dp[i+1][j],dp[i][j+1])& \text{if } x_i \ne y_j
\end{cases}
\end{aligned}
$$
Longest Common Increasing Subsequence
$$
dp[i][j]=x[0:i]和y[0:j]的最长公共上升子序列长度
$$
$$
dp[i][0] = dp[0][j] = 0
$$
$$
dp[i+1][j+1]=
\begin{aligned}
\begin{cases}
dp[i][j] + 1& \text{if } x_i = y_j \newline
\max(dp[i+1][j],dp[i][j+1])& \text{if } x_i \ne y_j
\end{cases}
\end{aligned}
$$
$$
dp[i][j]=x[0:i]到y[0:j]的最小操作次数
$$
$$
\begin{aligned}
dp[i][0] &= i \newline
dp[0][j] &= j
\end{aligned}
$$
$$
dp[i+1][j+1]=
\begin{aligned}
\begin{cases}
dp[i][j]& \text{if } x_i = y_j \newline
1+\min(dp[i+1][j],dp[i][j+1],dp[i][j])& \text{if } x_i \ne y_j
\end{cases}
\end{aligned}
$$
$$
dp[i][j]=只选前i个物品所能获得的最大价值
$$
$$
dp[0] = 0
$$
$$
dp[i]=
\begin{aligned}
\begin{cases}
dp[i-1] + v_i& \text{if } w + w_i \le W \newline
1+\min(dp[i+1][j],dp[i][j+1],dp[i][j])& \text{if } x_i \ne y_j
\end{cases}
\end{aligned}
$$
$$
dp[i][j]=s[i:j+1]是否是回文串
$$
$$
\begin{aligned}
&dp[i][i] = true
&dp[i][i+1] = true \quad \text{ if } s_i = s_{i+1}
\end{aligned}
$$
$$
dp[i][i+j]=dp[i+1][i+j-1] \land s_i = s_{i+j}
$$
121. 买卖股票的最佳时机
- 定义状态：$dp[i]$ 表示前 $i$ 天的最大利润。
- 状态转移：
$$
dp[i] = \max(dp[i-1], prices[i] - 前i-1天的最低价格)
$$
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int[] dp = new int[n];
int minPrice = prices[0];
for (int i = 1; i < n; i++) {
dp[i] = Math.max(dp[i - 1], prices[i] - minPrice);
minPrice = Math.min(minPrice, prices[i]);
}
return dp[n - 1];
}
}
|
- 空间优化：每一天的状态只与前一天的状态有关。
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public int maxProfit(int[] prices) {
int ans = 0;
int minPrice = Integer.MAX_VALUE;
for (int price : prices) {
ans = Math.max(ans, price - minPrice);
minPrice = Math.min(minPrice, price);
}
return ans;
}
}
|
122. 买卖股票的最佳时机 II
定义状态：$dp[i][0]$ 表示第 $i$ 天未持有股票的最大利润，$dp[i][1]$ 表示第 $i$ 天持有股票的最大利润。
状态转移：
- 未持有->未持有。
- 未持有->持有。（购买）
- 持有->未持有。（出售）
- 持有->持有。
$$
dp[i][0] = \max(dp[i-1][0],dp[i-1][1] + prices[i]) \newline
dp[i][1] = \max(dp[i-1][1],dp[i-1][0] - prices[i])
$$
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int[][] dp = new int[n][2];
dp[0][1] = -prices[0];
for (int i = 1; i < n; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}
return dp[n - 1][0];
}
}
|
- 空间优化：每一天的状态只与前一天的状态有关。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
// 最开始不可能持有股票，状态不存在，置为负无穷
int[] dp = { 0, Integer.MIN_VALUE };
for (int price : prices) {
int[] temp = {
Math.max(dp[0], dp[1] + price),
Math.max(dp[1], dp[0] - price)
};
dp = temp;
}
return dp[0];
}
}
|
123. 买卖股票的最佳时机 III
定义状态：
- $dp[i][0][0]$ 表示第 $i$ 天未持有股票且前 $i$ 天未进行过购买的最大利润。
- $dp[i][1][0]$ 表示第 $i$ 天未持有股票且前 $i$ 天进行过 1 次购买的最大利润。
- $dp[i][2][0]$ 表示第 $i$ 天未持有股票且前 $i$ 天进行过 2 次购买的最大利润。
- $dp[i][0][1]$ 表示第 $i$ 天持有股票且前 $i$ 天未进行过购买的最大利润。
- $dp[i][1][1]$ 表示第 $i$ 天持有股票且前 $i$ 天进行过 1 次购买的最大利润。
- $dp[i][2][1]$ 表示第 $i$ 天持有股票且前 $i$ 天进行过 2 次购买的最大利润。
状态转移：
- 未持有->未持有。
- 未持有->持有。（购买，交易数+1）
- 持有->未持有。（出售）
- 持有->持有。
$$
\begin{aligned}
dp[i][0][0] &= dp[i-1][0][0] \newline
dp[i][1][0] &= \max(dp[i-1][1][0],dp[i-1][1][1] + prices[i]) \newline
dp[i][2][0] &= \max(dp[i-1][2][0],dp[i-1][2][1] + prices[i]) \newline
dp[i][0][1] &= -\infty \newline
dp[i][1][1] &= \max(dp[i-1][1][1],dp[i-1][0][0] - prices[i]) \newline
dp[i][2][1] &= \max(dp[i-1][2][1],dp[i-1][1][0] - prices[i]) \newline
\end{aligned}
$$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int[][][] dp = new int[n][3][2];
dp[0][0][1] = -100000; // 防止溢出
dp[0][1][1] = -prices[0];
dp[0][2][1] = -prices[0];
for (int i = 1; i < n; i++) {
dp[i][0][0] = dp[i - 1][0][0];
dp[i][1][0] = Math.max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i]);
dp[i][2][0] = Math.max(dp[i - 1][2][0], dp[i - 1][2][1] + prices[i]);
dp[i][0][1] = -100000; // 防止溢出
dp[i][1][1] = Math.max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i]);
dp[i][2][1] = Math.max(dp[i - 1][2][1], dp[i - 1][1][0] - prices[i]);
}
return dp[n - 1][2][0];
}
}
|
- 空间优化：每一天的状态只与前一天的状态有关。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int maxProfit(int[] prices) {
int sell1 = 0; // 已经卖出 1 次的最大利润，等价于 dp[i][1][0]
int sell2 = 0; // 已经卖出 2 次的最大利润，等价于 dp[i][2][0]
int buyy1 = Integer.MIN_VALUE; // 已经买入 1 次的最大利润，等价于 dp[i][1][1]
int buyy2 = Integer.MIN_VALUE; // 已经买入 2 次的最大利润，等价于 dp[i][2][1]
for (int price : prices) {
sell2 = Math.max(sell2, buyy2 + price);
buyy2 = Math.max(buyy2, sell1 - price);
sell1 = Math.max(sell1, buyy1 + price);
buyy1 = Math.max(buyy1, -price);
}
return sell2;
}
}
|
188. 买卖股票的最佳时机 IV
定义状态：
- $dp[i][j][0]$ 表示第 $i$ 天未持有股票且前 $i$ 天进行过 $j$ 次购买的最大利润。
- $dp[i][j][1]$ 表示第 $i$ 天持有股票且前 $i$ 天进行过 $j$ 次购买的最大利润。
状态转移：
- 未持有->未持有。
- 未持有->持有。（购买，交易数+1）
- 持有->未持有。（出售）
- 持有->持有。
$$
\begin{aligned}
dp[i][0][0] &= dp[i-1][0][0] \newline
dp[i][j][0] &= \max(dp[i-1][j][0],dp[i-1][j][1] + prices[i]) \ (j \gt 0) \newline
dp[i][0][1] &= -\infty \newline
dp[i][j][1] &= \max(dp[i-1][j][1],dp[i-1][j-1][0] - prices[i]) \ (j \gt 0) \newline
\end{aligned}
$$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int maxProfit(int k, int[] prices) {
int n = prices.length;
if (n == 0) return 0;
int[][][] dp = new int[n][k + 1][2];
dp[0][0][1] = -100000; // 防止溢出
for (int i = 1; i <= k; i++) dp[0][i][1] = -prices[0];
for (int i = 1; i < n; i++) {
dp[i][0][0] = dp[i - 1][0][0];
dp[i][0][1] = -100000; // 防止溢出
for (int j = 1; j <= k; j++) {
dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
}
}
return dp[n - 1][k][0];
}
}
|
- 空间优化：每一天的状态只与前一天的状态有关。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int maxProfit(int k, int[] prices) {
int n = prices.length;
if (n == 0) return 0;
int[][] dp = new int[k + 1][2];
for (int i = 0; i <= k; i++)
dp[i][1] = -100000; // 防止溢出
for (int price : prices) {
for (int j = 1; j <= k; j++) {
dp[j][0] = Math.max(dp[j][0], dp[j][1] + price);
dp[j][1] = Math.max(dp[j][1], dp[j - 1][0] - price);
}
}
return dp[k][0];
}
}
|
309. 最佳买卖股票时机含冷冻期
定义状态：
- $dp[i][j][0]$ 表示第 $i$ 天未持有股票且前 $i$ 天进行过 $j$ 次购买的最大利润。
- $dp[i][j][1]$ 表示第 $i$ 天持有股票且前 $i$ 天进行过 $j$ 次购买的最大利润。
状态转移：
- 未持有->未持有。
- 未持有->持有。（购买，交易数+1）
- 持有->未持有。（出售）
- 持有->持有。
$$
\begin{aligned}
dp[i][0][0] &= dp[i-1][0][0] \newline
dp[i][j][0] &= \max(dp[i-1][j][0],dp[i-1][j][1] + prices[i]) \ (j \gt 0) \newline
dp[i][0][1] &= -\infty \newline
dp[i][j][1] &= \max(dp[i-1][j][1],dp[i-1][j-1][0] - prices[i]) \ (j \gt 0) \newline
\end{aligned}
$$
- 空间优化：每一天的状态只与前一天的状态有关。
714. 买卖股票的最佳时机含手续费
定义状态：
- $dp[i][j][0]$ 表示第 $i$ 天未持有股票且前 $i$ 天进行过 $j$ 次购买的最大利润。
- $dp[i][j][1]$ 表示第 $i$ 天持有股票且前 $i$ 天进行过 $j$ 次购买的最大利润。
状态转移：
- 未持有->未持有。
- 未持有->持有。（购买，交易数+1）
- 持有->未持有。（出售）
- 持有->持有。
$$
\begin{aligned}
dp[i][0][0] &= dp[i-1][0][0] \newline
dp[i][j][0] &= \max(dp[i-1][j][0],dp[i-1][j][1] + prices[i]) \ (j \gt 0) \newline
dp[i][0][1] &= -\infty \newline
dp[i][j][1] &= \max(dp[i-1][j][1],dp[i-1][j-1][0] - prices[i]) \ (j \gt 0) \newline
\end{aligned}
$$
- 空间优化：每一天的状态只与前一天的状态有关。
Longest Increasing Subsequence
动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
int ans = 1;
for (int i = 0; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
ans = Math.max(ans, dp[i]);
}
}
}
return ans;
}
|
贪心 + 二分查找
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
| /**
* list 中每个链表都是降序排列，只能将更小的值加入末尾
* 若均无法添加，则作为一个新链表加入 list
* 二分查找找到能够添加的下标最小的链表，然后加入
* 最后保证了每个链表的尾结点单调递增
* list 的大小即为最长子序列的长度
*/
int lengthOfLIS(int[] nums) {
int[] top = new int[nums.length];
int size = 0;
for (int num : nums) {
int left = 0;
int right = size;
while (left < right) {
int mid = left + (right - left) / 2;
if (top[mid] < num) {
left = mid + 1;
} else {
right = mid;
}
}
top[size] = num;
if (left == size) {
size++;
}
}
return size;
}
|
二分查找
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
| /**
* 数组 d[i]，表示长度为 i 的最长上升子序列的末尾元素的最小值
* 用 len 记录目前最长上升子序列的长度
*/
int lengthOfLIS(int[] nums) {
int[] dis = new int[nums.length];
int len = 0;
for (int num : nums) {
int left = 0;
int right = len;
while (left < right) {
int mid = left + (right - left) / 2;
if (dis[mid] < num) {
left = mid + 1;
} else {
right = mid;
}
}
dis[left] = num;
if (left == len) {
len++;
}
}
return len;
}
|
Longest Common Subsequence
1143. 最长公共子序列
583. 两个字符串的删除操作
516. 最长回文子序列
1092. 最短公共超序列
Longest Common Increasing Subsequence
力扣-0730-统计不同回文子序列
1035. 不相交的线
64. 最小路径和
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
for (int i = 1; i < m; i++) grid[i][0] += grid[i - 1][0];
for (int j = 1; j < n; j++) grid[0][j] += grid[0][j - 1];
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
return grid[m - 1][n - 1];
}
}
|
473. 火柴拼正方形
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
| class Solution {
public boolean makesquare(int[] matchsticks) {
int totalLen = Arrays.stream(matchsticks).sum();
if (totalLen % 4 != 0) {
return false;
}
int len = totalLen / 4, n = matchsticks.length;
int[] dp = new int[1 << n];
Arrays.fill(dp, -1);
dp[0] = 0;
for (int s = 1; s < (1 << n); s++) {
for (int k = 0; k < n; k++) {
if ((s & (1 << k)) == 0) {
continue;
}
int s1 = s & ~(1 << k);
if (dp[s1] >= 0 && dp[s1] + matchsticks[k] <= len) {
dp[s] = (dp[s1] + matchsticks[k]) % len;
break;
}
}
}
return dp[(1 << n) - 1] == 0;
}
}
|