专题-B-动态规划
DP 问题的一般思路
- DP 定义 ——有时 DP 的更新很难严格遵循定义，需要额外变量保存全局最优结果
- 初始化 ——初始值可以通过一个简单的特例来确定
- 递推公式 + 边界条件
- DP 优化 （可选）
Reference
- 常见的动态规划问题分析与求解 - 五岳 - 博客园
- 什么是动态规划？动态规划的意义是什么？ - 知乎
背包问题
【注】关于“恰好装满”
- 如果要求恰好装满背包，可以在初始化时将
dp[0] / dp[i][0]初始化0，其他初始化为-INF。这样即可保证最终得到的dp[N] / dp[N][M]是一种恰好装满背包的解； - 如果不要求恰好装满，则全部初始化为
0即可。 - 可以这样理解：初始化的 dp 数组实际上就是在没有任何物品可以放入背包时的合法状态。
- 如果要求背包恰好装满，那么此时只有容量为 0 的背包可能被价值为 0 的物品“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是
-INF。 - 如果背包并非必须被装满，那么任何容量的背包都有一个合法解，即“什么都不装”，这个解的价值为0，所以初始时状态的值也全部为 0 。
- 如果要求背包恰好装满，那么此时只有容量为 0 的背包可能被价值为 0 的物品“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是
01 背包
问题描述
有 n 个重量个价值分别为 w_i, v_i 的物品。
从这些物品中选出总重量不超过 W 的物品，使其总价值最大。
示例
1 // 用例数
5 10 // 物品数 背包容量 N <= 1000 , V <= 1000
1 2 3 4 5
5 4 3 2 1
14二维 DP（无优化）
定义：
dp[i][j] := 从前 i 个物品中选取总重量不超过 j 的物品时总价值的最大值i从 1 开始计，包括第i个物品初始化
dp[0][j] = 0状态转移
dp[i][j] = dp[i-1][j] if j < w[i] （当前剩余容量不够放下第 i 个物品） = max{ else （取以下两种情况的最大值） dp[i-1][j], // 不拿第 i 个物品 dp[i-1][j-w[i]] + w[j] // 拿第 i 个物品 }// HDOJ 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2602 int solve(int N, int V, vector<int>& v, vector<int>& w) { vector<vector<int> > dp(N + 1, vector<int>(V + 1, 0)); // 不要求装满，初始化为 0 即可 // 核心代码 for (int i = 1; i <= N; i++) { for (int j = 0; j <= V; j++) { // 可能存在重量为 0，但有价值的物品 if (w[i] > j) // 如果当前物品的重量大于剩余容量 dp[i][j] = dp[i - 1][j]; else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]); } } return dp[N][V]; }
int main() { int T; // 用例数 scanf("%d", &T); while (T--) { int N, V; // N: 物品数量；V: 背包容量 scanf("%d%d", &N, &V); vector v(N + 1, 0); // 保存每个物品的价值 vector w(N + 1, 0); // 保存每个物品的重量 for (int i = 1; i <= N; i++) scanf("%d", &v[i]); for (int i = 1; i <= N; i++) scanf("%d", &w[i]);
int ans = solve(N, V, v, w);
printf("%d\n", ans);
}
return 0;}
#### 二维 DP（滚动数组）
- 在上述递推式中，`dp[i+1]` 的计算实际只用到了 `dp[i+1]` 和 `dp[i]`；
- 因此可以结合**奇偶**，通过两个数组滚动使用来实现重复利用。
```C++
// HDOJ 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2602
int solve(int N, int V, vector<int>& v, vector<int>& w) {
//vector<vector<int> > dp(N + 1, vector<int>(V + 1, 0)); // 不要求装满，初始化为 0 即可
vector<vector<int> > dp(2, vector<int>(V + 1, 0)); // N+1 -> 2
// 核心代码
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= V; j++) { // 可能存在重量为 0，但有价值的物品
if (w[i] > j) // 如果当前物品的重量大于剩余容量
dp[i & 1][j] = dp[(i - 1) & 1][j];
else
dp[i & 1][j] = max(dp[(i - 1) & 1][j], dp[(i - 1) & 1][j - w[i]] + v[i]);
}
}
return dp[N & 1][V]; // 这里别忘了 N & 1
}
// main 函数略一维 DP
- 定义：
dp[j] := 重量不超过 j 公斤的最大价值 - 递推公式
dp[j] = max{dp[j], dp[j-w[i]] + v[i]} 若 j > w[i]
// HDOJ 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2602
// 一维 DP（滚动数组）
int solve(int N, int V, vector<int>& v, vector<int>& w) {
vector<int> dp(V + 1, 0);
// 核心代码
for (int i = 1; i <= N; i++) {
for (int j = V; j >= w[i]; j--) { // 递推方向发生了改变
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
return dp[V];
}
// main 函数略完全背包
问题描述
01 背包中每个物品只有一个，所以只存在选或不选；
完全背包中每个物品可以选取任意件。
注意：本题要求是背包恰好装满背包时，求出最大价值总和是多少。如果不能恰好装满背包，输出 NO二维 DP（无优化）
直观思路：在 01 背包的基础上在加一层循环
递推关系：
dp[0][j] = 0 dp[i][j] = max{dp[i - 1][j - k * w[i]] + k * v[i] | 0 <= k}for (int i = 1; i <= N; i++) { for (int j = 0; j <= V; j++) { // 可能存在重量为 0 的物品 for (int k = 0; k * w[i] <= j; k++) dp[i][j] = max(dp[i][j], dp[i-1][j - k*w[i]] + k*v[i]); } }- 关于
k的循环最坏可能从 0 到V，因此时间复杂度为O(N*V^2)
- 关于
注意到：
dp[i][j] = max{dp[i - 1][j - k*w[i]] + k*v[i] | 0 <= k} ------ = max{dp[i - 1][j], max{dp[i - 1][j - k*w[i]] + k*v[i]} | 1 <= k} ------ = max{dp[i - 1][j], max{dp[i - 1][(j-w[i]) - k*w[i]] + k*v[i] | 0 <= k} + v[i]} -------- ------ ------ --------------------------------------------------- = max{dp[i - 1][j], dp[i][j - w[i]] + v[i]} ---------------for (int i = 1; i <= N; i++) { for (int j = 0; j <= V; j++) { if (w[i] > j) dp[i][j] = dp[i - 1][j]; else dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i]); // dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]); // 对比 01 背包 // ---------（唯一区别） } }完整代码
注意，这里要求的是恰好装满时的情况，所以需要将
dp[i][0]全部初始化为 0，其他初始化为-INF以下代码因超内存无法通过 NYOJ 311；
可以 AC 的代码，请参考 完全背包（一维 DP） 和 完全背包（滚动数组）
// NYOJ 311 会报超内存，所以无法测试 #include <cstdio> #include <vector> #include <algorithm> using namespace std;const int inf = 0x80000000;
void solve() { int T; scanf("%d", &T); while (T--) { int N, V; // N 表示物品种类的数目，V 表示背包的总容量 scanf("%d%d", &N, &V); vector w(N + 1), v(N + 1); // w 表示重量，v 表示价值 for (int i = 1; i <= N; i++) scanf("%d%d", &w[i], &v[i]);
vector<vector<int> > dp(N + 1, vector<int>(V + 1, inf)); for (int i = 0; i <= N; i++) dp[i][0] = 0; for (int i = 1; i <= N; i++) { for (int j = 0; j <= V; j++) { if (j < w[i]) dp[i][j] = dp[i - 1][j]; else dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i]); } } if (dp[N][V] > 0) printf("%d\n", dp[N][V]); else puts("NO"); }}
int main() { solve(); return 0; }
二维 DP（滚动数组）
// NYOJ 311-完全背包: http://nyoj.top/problem/311 （未通过测试，报运行时错误）
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
void solve3() {
const int MAX_V = 50000 + 10;
const int inf = 0x3f3f3f3f;
int T;
scanf("%d", &T);
while (T--) {
int N, V; // M 表示物品种类的数目，V 表示背包的总容量
scanf("%d%d", &N, &V);
//vector<int> w(N + 1), v(N + 1); // w 表示重量，v 表示价值
//for (int i = 1; i <= N; i++)
// scanf("%d%d", &w[i], &v[i]);
//vector<vector<int> > dp(2, vector<int>(V + 1, -inf));
int dp[2][MAX_V];
for (int i = 0; i < 2; i++) {
fill(dp[i], dp[i] + MAX_V, -inf);
dp[i][0] = 0;
}
for (int i = 1; i <= N; i++) {
int w, v;
scanf("%d%d", &w, &v);
for (int j = 0; j <= V; j++) {
if (j < w)
dp[i & 1][j] = dp[(i - 1) & 1][j];
else
dp[i & 1][j] = max(dp[(i - 1) & 1][j], dp[i & 1][j - w] + v);
}
}
if (dp[N][V] > 0)
printf("%d\n", dp[N & 1][V]);
else
puts("NO");
}
}
int main() {
solve3();
return 0;
}一维 DP
核心代码与 01 背包一致，只有第二层循环的递推方向不同
完整代码
// NYOJ 311-完全背包: http://nyoj.top/problem/311 #include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; const int MAX_V = 50000 + 10; const int inf = 0x80000000; void solve2() { int T; scanf("%d", &T); while (T--) { int N, V; // M 表示物品种类的数目，V 表示背包的总容量 scanf("%d%d", &N, &V); //vector<int> w(N + 1), v(N + 1); // w 表示重量，v 表示价值 //for (int i = 1; i <= N; i++) // scanf("%d%d", &w[i], &v[i]); //vector<int> dp(V + 1, inf); // 注意 NYOJ 的系统开辟稍大的 vector 就会导致超时 int dp[MAX_V]; fill(dp, dp + MAX_V, inf); dp[0] = 0; for (int i = 1; i <= N; i++) { int w, v; scanf("%d%d", &w, &v); // 避免开辟新的内存 for (int j = w; j <= V; j++) { dp[j] = max(dp[j], dp[j - w] + v); } } if (dp[V] > 0) printf("%d\n", dp[V]); else puts("NO"); } } int main() { solve2(); return 0; }
多重背包 TODO
硬币问题
硬币找零
LeetCode - 322. 零钱兑换
问题描述
给定不同面额的硬币 coins 和一个总金额 amount。
编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
示例 2:
输入: coins = [2], amount = 3
输出: -1
说明:
你可以认为每种硬币的数量是无限的。思路
定义：
dp[i] := 组成总金额 i 时的最少硬币数初始化：
dp[i] = 0 若 i=0 = INF 其他状态转移
dp[j] = min{ dp[j-coins[i]] + 1 | i=0,..,n-1 } 其中 coins[i] 表示硬币的币值，共 n 种硬币
C++
class Solution {
public:
int coinChange(vector<int>& coins, int n) {
int INF = n + 1;
vector<int> dp(n+1, INF);
dp[0] = 0;
for (auto c: coins) {
for (int i=c; i<=n; i++) { // i >= c
dp[i] = min(dp[i], dp[i-c] + 1);
}
}
return dp[n] < INF ? dp[n] : -1;
}
};硬币组合
LeetCode - 518. 零钱兑换 II
C++
class Solution {
public:
int change(int n, vector<int>& coins) {
int m = coins.size();
vector<int> dp(n+1, 0);
dp[0] = 1;
for (auto c: coins) {
for (int i = c; i <= n; i++) {
dp[i] += dp[i - c];
}
}
return dp[n];
}
};最长公共子序列（LCS）
最长公共子序列_牛客网
- 求两个序列的最长公共字序列
- 示例：s1: "BDCABA" 与 s2："ABCBDAB" 的一个最长公共字序列为 "BCBA"
- 最长公共子序列不唯一，但是它们的长度是一致的
- 子序列不要求连续
思路
DP 定义
- 记
s[0:i] := s 长度为 i 的**前缀** - 定义
dp[i][j] := s1[0:i] 和 s2[0:j] 最长公共子序列的长度
- 记
DP 初始化
dp[i][j] = 0 当 i=0 或 j=0 时DP 更新
- 当
s1[i] == s2[j]时dp[i][j] = dp[i-1][j-1] + 1 - 当
s1[i] != s2[j]时dp[i][j] = max(dp[i-1][j], dp[i][j-1])
- 当
完整递推公式
dp[i][j] = 0 当 i=0 或 j=0 时 = dp[i-1][j-1] + 1 当 `s1[i-1] == s2[j-1]` 时 = max(dp[i-1][j], dp[i][j-1]) 当 `s1[i-1] != s2[j-1]` 时Code - C++
class LCS { public: int findLCS(string A, int n, string B, int m) { vector<vector<int> > dp(n+1, vector<int>(m+1, 0)); // 已经初始化为全 0，就不必再手动初始化 DP 了 for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) if (A[i-1] == B[j-1]) // 注意下标问题 dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i][j-1], dp[i-1][j]); return dp[n][m]; } };
最长公共子串
最长公共子串_牛客网
题目描述
对于两个字符串，请设计一个时间复杂度为`O(m*n)`的算法，求出两串的最长公共子串的长度。
（这里的 m 和 n 为两串的长度）思路 - 暴力求解
Longest common substring problem - Wikipedia
暴力求解思路：每当找到一对元素相同时就斜向比较
class LongestSubstring {
public:
int findLongest(string A, int n, string B, int m) {
int ret = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int tmp_ret = 0;
if (A[i] == B[j]) { // 每当找到一对元素相同
tmp_ret += 1; // 斜向比较
int tmp_i = i + 1;
int tmp_j = j + 1;
while (tmp_i < n && tmp_j < m && A[tmp_i++] == B[tmp_j++]) // 注意边界
tmp_ret++;
}
ret = max(ret, tmp_ret); // 记录最大
}
}
return ret;
}
};- 注意：如果两个串完全相同的话，时间复杂度将退化为
O(N^3)
思路 - DP
DP 定义
- 记
s[0:i] := s 长度为 i 的**前缀** 定义dp[i][j] := s1[0:i] 和 s2[0:j] 最长公共子串的长度dp[i][j]只有当s1[i] == s2[j]的情况下才是s1[0:i] 和 s2[0:j] 最长公共子串的长度
- 记
DP 初始化
dp[i][j] = 0 当 i=0 或 j=0 时DP 更新
dp[i][j] = dp[i-1][j-1] + 1 if s[i] == s[j] = ; else passCode
class LongestSubstring { public: int findLongest(string A, int n, string B, int m) { vector<vector<int> > dp(n + 1, vector<int>(m + 1, 0)); // 已经初始化为全 0，就不必再手动初始化 DP 了 int ret = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (A[i - 1] == B[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; ret = max(ret, dp[i][j]); // 相比最长公共子序列，增加了这行 } else ; // 去掉了这行 return ret; } };DP 优化：空间复杂度
O(N)好不容易找到的优化为
O(N)的代码；多数优化直接优化到了O(1)因为内层循环是逆序的，所以有点不好理解，可以画一个矩阵手推 DP 的更新过程，很巧妙
class LongestSubstring { public: int findLongest(string A, int n, string B, int m) { if (n < m) { swap(n, m); swap(A, B); } vector<int> dp(m, 0); int ret = 0; for (int i = 0; i < n; i++) { for (int j = m - 1; j >= 0; j--) { if (A[i] != B[j]) { dp[j] = 0; } else { if (i != 0) { dp[j] = dp[j - 1] + 1; } else { dp[j] = 1; } } ret = max(ret, dp[j]); } } return ret; } };
DP 优化：空间复杂度
O(1)- 两个字符串的比较总是按一行一行或一列一列来比较，因此至少要保存一行的数据
- 而如果是按照斜向遍历，其实只要保存一个数据即可
斜向遍历的策略很多，下面的代码是从右上角（
row=0, col=m-1）开始遍历class LongestSubstring { public: int findLongest(string A, int n, string B, int m) { int ret = 0; for (int row = 0, col = m - 1; row < n;) { int i = row; int j = col; int dp = 0; while (i < n && j < m) { if (A[i++] == B[j++]) // 注意：无论走哪个分支，i 和 j 都会 ++ 一次 dp += 1; else dp = 0; ret = max(ret, dp); } if (col > 0) col--; else row++; } return ret; } };上述代码其实就是把下面的两段循环合并了
class LongestSubstring { public: int findLongest(string A, int n, string B, int m) { int ret = 0; int dp; for (int col = m-1; col >= 0; col--) { dp = 0; for (int i = 0, j = col; i < n && j < m; i++, j++) { if (A[i] == B[j]) dp += 1; else dp = 0; ret = max(ret, dp); } } for (int row = 0; row < n; row++) { dp = 0; for (int i = row, j = 0; i < n && j < m; i++, j++) { if (A[i] == B[j]) dp += 1; else dp = 0; ret = max(ret, dp); } } return ret; } };
最长递增子序列（LIS）
最长递增子序列_牛客网
最长上升子序列 - LeetCode
牛客假设给定的数组中不存在重复元素，LeetCode 可能存在重复元素
问题描述
对于一个数字序列，请设计一个复杂度为O(nlogn)的算法，返回该序列的最长上升子序列的长度
测试样例：
[2,1,4,3,1,5,6],7
返回：
4
说明：
[1,3,5,6] 是其中一个最长递增子序列思路0 - O(N^2)
- LIS 可以转化成 LCS (最长公共子序列) 问题
- 用另一个序列保存给定序列的排序结果 -
O(NlogN) - 则问题转化为求这两个序列的 LCS 问题 -
O(N^2)
思路1 - O(N^2)解法
DP 定义
- 记
nums[0:i] := 序列 nums 的前 i 个元素构成的子序列 - 定义
dp[i] := nums[0:i] 中 LIS 的长度 - 实际并没有严格按照这个定义，中间使用一个变量记录当前全局最长的 LIS
- 记
DP 初始化
dp[:] = 1 // 最长上升子序列的长度最短为 1DP 更新 -
O(N^2)的解法dp[i] = max{dp[j]} + 1, if nums[i] > nums[j] = max{dp[j]}, else where 0 <= j < i如果只看这个递推公式，很可能会写出如下的错误代码
错误代码（点击展开）
// 牛客网 class AscentSequence { public: int findLongest(vector<int> nums, int n) { vector<int> dp(n, 1); for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1); else dp[i] = max(dp[i], dp[j]); } return dp[n-1]; } };- 这段代码的问题在于
dp[i]应该等于max{dp[j]}对应的那个dp[j]+1，且只增加一次 - 这么写可能会导致
dp[i]被增加多次
- 这段代码的问题在于
下面是网上比较流行的一种递推公式
dp[i] = dp[j] + 1, if nums[i] > nums[j] && dp[i] < dp[j] + 1 = pass, else where 0 <= j < i- 注意：此时并没有严格按照定义处理 dp，它只记录了当
nums[i] > nums[j] && dp[i] < dp[j] + 1时的 LIS；不满足该条件的情况跳过了；所以需要额外一个变量记录当前已知全局的 LIS
- 注意：此时并没有严格按照定义处理 dp，它只记录了当
Code
// 牛客网 class AscentSequence { public: int findLongest(vector<int> nums, int n) { vector<int> dp(n, 1); int ret = 1; for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) if (nums[i] > nums[j] && dp[i] < dp[j] + 1) dp[i] = dp[j] + 1; ret = max(ret, dp[i]); } return ret; } };
思路2 - O(NlogN)
该解法的思想是：长度为
i的 LIS 的尾元素应该大于长度为i-1的尾元素DP 定义
- 定义
dp[i] := 长度为 i 的 LIS 的最小尾元素
- 定义
DP 更新
- 二分查找 nums[j] 在 dp 中的
upper_bound 位置lower_bound 位置- upper_bound 位置指的是序列中第一个大于 nums[j] 的元素所在的位置
- lower_bound 位置指的是序列中第一个大于等于 nums[j] 的元素所在的位置
- C++ 中分别实现了 upper_bound 和 lower_bound，定义在
<algorithm>中 - 如果在末尾，则插入；反之则替换
- upper_bound 只能用于不存在重复元素的情况；而 lower_bound 可以兼容两种情况
- 二分查找 nums[j] 在 dp 中的
Code
// 牛客网 class AscentSequence { public: int findLongest(const vector<int>& nums, int n) { vector<int> dp; for (int j = 0; j < n; j++) { // 这里用 upper_bound 也可以 auto it = lower_bound(dp.begin(), dp.end(), nums[j]); if (it == dp.end()) dp.push_back(nums[j]); else *it = nums[j]; } return dp.size(); } }; // LeetCode class Solution { public: int lengthOfLIS(vector<int>& nums) { int n = nums.size(); vector<int> dp; for (int j = 0; j < n; j++) { // 这里只能使用 lower_bound auto it_l = lower_bound(dp.begin(), dp.end(), nums[j]); // auto it_u = upper_bound(dp.begin(), dp.end(), nums[j]); if (it_l == dp.end()) dp.push_back(nums[j]); else *it_l = nums[j]; } return dp.size(); } };
最长回文子序列
最长回文子序列 - LeetCode
问题描述
给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。
示例 1:
输入:
"bbbab"
输出:
4
一个可能的最长回文子序列为 "bbbb"。思路
相比最长回文子串，最长回文子序列更像最长公共子序列，只是改变了循环方向
DP 定义
- 记
s[i:j] := 字符串 s 在区间 [i:j] 上的子串 - 定义
dp[i][j] := s[i:j] 上回文序列的长度
- 记
DP 初始化
dp[i][i] = 1 // 单个字符也是一个回文序列DP 更新
dp[i][j] = dp[i+1][j-1] + 2, if s[i] == s[j] = max(dp[i+1][j], dp[i][j-1]), else 比较一下 LCS 的递推公式 dp[i][j] = 0 当 i=0 或 j=0 时 = dp[i-1][j-1] + 1 当 `s1[i-1] == s2[j-1]` 时 = max(dp[i-1][j], dp[i][j-1]) 当 `s1[i-1] != s2[j-1]` 时Code
class Solution { public: int longestPalindromeSubseq(string s) { int n = s.length(); vector<vector<int>> dp(n, vector<int>(n, 0)); for (int i = 0; i < n; i++) dp[i][i] = 1; for (int j = 1; j < n; j++) // 子串结束位置 for (int i = j-1; i >=0; i--) { // 子串开始位置 if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2; else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); } return dp[0][n - 1]; } };
最长回文子串
最长回文子串_牛客网
最长回文子串 - LeetCode
牛客网只需要输出长度；LeetCode 还需要输出一个具体的回文串
问题描述
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。思路 - O(N^2)
DP 定义
- 记
s[i:j] := 字符串 s 在区间 [i:j] 上的子串 - 定义
dp[i][j] := s[i:j] 是否是一个回文串
- 记
DP 初始化
dp[i][i] = 1 // 单个字符也是一个回文串DP 更新
dp[i][j] = dp[i+1][j-1], if s[i] == s[j] = 0, else 注意到：如果 j - i < 2 的话（比如 j=2, i=1），dp[i+1][j-1]=dp[2][1] 会出现不符合 DP 定义的情况 所以需要添加边界条件 dp[i][i+1] = 1, if s[i] == s[i+1] = 0, else 该边界条件可以放在初始化部分完成；但是建议放在递推过程中完成过更好（为了兼容牛客和LeetCode）Code
// 牛客网 AC class Palindrome { public: int getLongestPalindrome(const string& s, int n) { vector<vector<int> > dp(n, vector<int>(n, 0)); // 初始化 for (int i=0; i<n-1; i++) dp[i][i] = 1; int len = 1; for (int j=1; j<n; j++) { // 子串结束位置 for (int i=j-1; i>=0; i--) { // 子串开始位置 if (j-i < 2) dp[i][j] = (s[i]==s[j]) ? 1 : 0; else if (s[i]==s[j]) dp[i][j] = dp[i+1][j-1]; else dp[i][j] = 0; // 因为 dp 全局初始化就是 0，这里其实可以不写 if (dp[i][j] && j-i+1 > len) len = j-i+1; } } return len; } }; // LeetCode - 只要添加一个记录开始位置的变量即可 class Solution { public: string longestPalindrome(string s) { int n = s.length(); vector<vector<int> > dp(n, vector<int>(n, 0)); // 初始化 for (int i=0; i<n-1; i++) dp[i][i] = 1; int len = 1; int beg = 0; // 记录开始位置 for (int j=1; j<n; j++) { // 子串结束位置 for (int i=j-1; i>=0; i--) { // 子串开始位置 if (j-i < 2) dp[i][j] = (s[i]==s[j]) ? 1 : 0; else if (s[i]==s[j]) dp[i][j] = dp[i+1][j-1]; else dp[i][j] = 0; // 因为 dp 全局初始化就是 0，这里其实可以不写 if (dp[i][j] && j-i+1 > len) { beg = i; // 保存开始位置 len = j-i+1; } } } return s.substr(beg, len); // 截取子串 } };
Manacher 算法 - O(N)
算法-最长回文子串(Manacher算法) - 琼珶和予 - 博客园
最大连续子序列和
最大连续子序列_牛客网
牛客网要求同时输出最大子序列的首尾元素
思路 - 基本问题：只输出最大连续子序列和
DP 定义
- 记
a[0:i] := 序列 a 在区间 [0:i] 上的子序列 - 定义
dp[i] := a[0:i] 上的最大子序列和 - 实际并没有严格按照上面的定义，中间使用一个变量记录当前全局的最大连续子序列和
- 记
DP 初始化
dp[0] = a[0]DP 更新
// 只要 dp[i] > 0 就一直累加下去，一旦小于 0 就重新开始 dp[i] = dp[i-1] + a[i], if dp[i-1] > 0 = a[i], else ret = max{ret, dp[i]} // 只要大于 0 就累加会导致 dp[i] 保存的并不是 a[0:i] 中的最大连续子序列和 // 所以需要一个变量保存当前全局的最大连续子序列和直观实现-无优化-空间复杂度`O(N)`（点击展开）
void foo() { int n; while (cin >> n) { vector<int> a(n); for (int i = 0; i<n; i++) cin >> a[i]; vector<int> dp(n); dp[0] = a[0]; int ret = a[0]; for (int i = 1; i < n; i++) { if (dp[i - 1] > 0) dp[i] = dp[i - 1] + a[i]; else dp[i] = a[i]; ret = max(ret, dp[i]); } cout << ret << endl; } } /* 输入 5 1 5 -3 2 4 6 1 -2 3 4 -10 6 4 -3 -1 -2 -5 输出 9 7 -1 */DP 优化
注意到每次递归实际只用到了
dp[i-1]，实际只要用到一个变量，空间复杂度O(1)void foo2() { int n; while (cin >> n) { vector<int> a(n); for (int i = 0; i<n; i++) cin >> a[i]; int ret = INT_MIN; int max_cur = 0; for (int i = 0; i < n; i++) { if (max_cur > 0) // 如果大于 0 就一直累加 max_cur += a[i]; else // 一旦小于 0 就重新开始 max_cur = a[i]; if (max_cur > ret) // 保存找到的最大结果 ret = max_cur; // 以上可以简写成下面两行代码 //max_cur = max(max_cur + a[i], a[i]); //ret = max(ret, max_cur); } cout << ret << endl; } }
思路 - 输出区间/首尾
增加两个变量即可
注意：题目要求，如果序列中全是负数，则输出 0，以及整个序列的首尾元素
// 牛客网 AC #include <iostream> #include <cstdio> #include <vector> #include <climits> using namespace std; void foo3() { int n; while (cin >> n && n) { vector<int> a(n); for (int i = 0; i<n; i++) cin >> a[i]; int ret = INT_MIN; int max_cur = 0; int beg = a[0], end = a[n-1]; // 输出首尾 // int beg = 0, end = n-1; // 输出区间 int tmp_beg; // 保存临时 beg for (int i = 0; i < n; i++) { if (max_cur > 0) { max_cur += a[i]; } else { max_cur = a[i]; tmp_beg = a[i]; // tmp_beg = i; } if (max_cur > ret) { // > 表明保存的是第一次出现的最大和，>= 则为最后一次（未验证） ret = max_cur; beg = tmp_beg; end = a[i]; // 输出首尾 // end = i; // 输出区间 } } if (ret < 0) printf("%d %d %d\n", 0, a[0], a[n-1]); // printf("%d %d %d\n", 0, 0, n-1); else printf("%d %d %d\n", ret, beg, end); } } int main() { foo3(); return 0; }
编辑距离
LeetCode-编辑距离
问题描述
给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例:
输入: word1 = "horse", word2 = "ros"
输出: 3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')- 注意：编辑距离指的是将 word1 转换成 word2
思路
用一个 dp 数组维护两个字符串的前缀编辑距离
DP 定义
- 记
word[0:i] := word 长度为 i 的**前缀子串** - 定义
dp[i][j] := 将 word1[0:i] 转换为 word2[0:j] 的操作数
- 记
初始化
dp[i][0] = i // 每次从 word1 删除一个字符 dp[0][j] = j // 每次向 word1 插入一个字符递推公式
word1[i] == word1[j]时dp[i][j] = dp[i-1][j-1]word1[i] != word1[j]时，有三种更新方式，取最小// word[1:i] 表示 word 长度为 i 的前缀子串 dp[i][j] = min({ dp[i-1][j] + 1 , // 将 word1[1:i-1] 转换为 word2[1:j] 的操作数 + 删除 word1[i] 的操作数(1) dp[i][j-1] + 1 , // 将 word1[0:i] 转换为 word2[0:j-1] 的操作数 + 将 word2[j] 插入到 word1[0:i] 之后的操作数(1) dp[i-1][j-1] + 1 }) // 将 word1[0:i-1] 转换为 word2[0:j-1] 的操作数 + 将 word1[i] 替换为 word2[j] 的操作数(1)
C++
class Solution { public: int minDistance(string word1, string word2) { int m = word1.length(); int n = word2.length(); vector<vector<int> > dp(m + 1, vector<int>(n + 1, 0)); // 初始化 dp for (int i = 1; i <= m; i++) dp[i][0] = i; for (int j = 1; j <= n; j++) dp[0][j] = j; // 更新 dp for (int i = 1; i <=m; i++) for (int j = 1; j <= n; j++) if (word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1]; else dp[i][j] = min({ dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] }) + 1; return dp[m][n]; } };DP 优化
- 注意到每次更新
dp[i][j]只需要用到dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]。因此实际上不需要用到二维 DP - 具体见下方代码
Code - 优化为一维 DP（点击展开）
class Solution { public: int minDistance(string word1, string word2) { int m = word1.length(), n = word2.length(); vector<int> cur(m + 1, 0); for (int i = 1; i <= m; i++) cur[i] = i; for (int j = 1; j <= n; j++) { int pre = cur[0]; cur[0] = j; for (int i = 1; i <= m; i++) { int temp = cur[i]; if (word1[i - 1] == word2[j - 1]) cur[i] = pre; else cur[i] = min(pre + 1, min(cur[i] + 1, cur[i - 1] + 1)); pre = temp; } } return cur[m]; } };- 注意到每次更新
矩阵中的最大正方形
LeetCode-221. 最大正方形
问题描述
在一个由 0 和 1 组成的二维矩阵 M 内，找到只包含 1 的最大正方形，并返回其面积。
示例:
输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出:
4思路
- DP 定义：
dp[i][j] := 以 M[i][j] 为正方形**右下角**所能找到的最大正方形的边长- 注意保存的是边长
- 因为
dp保存的不是全局最大值，所以需要用一个额外变量更新结果
- 初始化
dp[i][0] = M[i][0] dp[0][j] = M[0][j] - 递推公式
dp[i][j] = min{dp[i-1][j], dp[i][j-1], dp[i-1][j-1]} + 1 若 M[i][j] == 1 = 0 否则注意到，本题的递推公式与 编辑距离 完全一致
C++
class Solution {
public:
int maximalSquare(vector<vector<char>>& M) {
if (M.empty() || M[0].empty())
return 0;
auto row = M.size();
auto col = M[0].size();
vector<vector<int> > dp(row, vector<int>(col, 0));
int mx = 0;
for (int i = 0; i < row; i++) {
dp[i][0] = M[i][0] - '0';
mx = max(mx, dp[i][0]); // 别忘了这里也要更新 mx
}
for (int j = 0; j < col; j++) {
dp[0][j] = M[0][j] - '0';
mx = max(mx, dp[0][j]); // 别忘了这里也要更新 mx
}
for (int i=1; i<row; i++)
for (int j = 1; j < col; j++) {
if (M[i][j] == '0')
dp[i][j] = 0;
else {
dp[i][j] = min({ dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] }) + 1;
mx = max(mx, dp[i][j]); // 更新 mx
}
}
return mx * mx;
}
};鹰蛋问题
Power Eggs http://acm.zcmu.edu.cn/JudgeOnline/problem.php?id=1894
问题描述
教授手上有`M`个一模一样的鹰蛋，教授想研究这些蛋的硬度`E`，测试方法是将蛋从高为`N`层的楼上不断自由落下；
每个蛋在`E+1`层及以上掉下都会碎，而在`E`层及以下不会碎；每个蛋可以重复测试直到它碎了为止。
例如：蛋从第 1 层掉下碎了，则`E=0`；蛋从第`N`层掉下未碎，则`E=N`。
求在给定`M`和`N`下为了确定`E`在**最坏情况下**需要测试的最少次数。
如果比较的次数大于 32，输出 "Impossible"。
范围：1 ≤ N ≤ 2000000007，1 ≤ K ≤ 32
示例：`N=10, K=1`，则`ans=10`
说明：如果只有一个蛋，那么只能将这个蛋一层层往上尝试；
因此在最坏情况下，它最少要测试 10 次才能确定 `E`分析
- 如果只有
M=1个蛋，那么只能从第一层开始一层一层往上尝试，最坏情况下的最少次数为N - 如果蛋的数量足够多，那么问题转变为二分查找，最坏情况下的最少次数为
logN上取整
思路
DP 定义：
dp[i][j] := i 个蛋比较 j 次所能确定的最高楼层DP 初始化
dp[i][1] = 1 // i 个蛋比较 1 次所能确定的最高楼层是 1 dp[1][j] = j // 1 个蛋比较 j 次所能确定的最高楼层为 jDP 更新
dp[i][j] = dp[i][j-1] + dp[i-1][j-1] + 1说明：TODO（不理解是如何得到这个递推式的）
C++
// OJ 地址：http://acm.zcmu.edu.cn/JudgeOnline/problem.php?id=1894 #include <cstdio> typedef long long LL; const int MAX_K = 32 + 1; const int MAX_T = 32 + 1; LL dp[MAX_K][MAX_T]; // 使用 LL 防止溢出，long 不保证比 int 更大 // dp[i][j] := i 个蛋比较 j 次所能确定的最高楼层 void init() { // 初始化 for (int i = 1; i < MAX_K; i++) dp[i][1] = 1; for (int j = 1; j < MAX_T; j++) dp[1][j] = j; // 更新 for (int i = 2; i < MAX_K; i++) for (int j = 2; j < MAX_T; j++) dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] + 1; } void solve() { init(); //printf("%lld", dp[32][32]); // 4294967295 == 2^32 - 1，用 int 会溢出 int T; // 1 ≤ T ≤ 10000 scanf("%d", &T); while (T--) { int N, K; // 1 ≤ N ≤ 2000000007 < 2^31, 1 ≤ K ≤ 32 scanf("%d %d", &N, &K); int ret = 0; for (int j = 1; j < MAX_T; j++) { // 注意：dp[i][j] 表示的是 i 个蛋比较 j 次所能确定的最高楼层 if (dp[K][j] >= N) { ret = j; break; } } if (ret) printf("%d\n", ret); else puts("Impossible"); } } int main() { solve(); return 0; }
Reference
- 从《鹰蛋》一题浅析对动态规划算法的优化_百度文库