单序列型 DP
LC 300 最长递增子序列（LIS）
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
分析：
自然想到定义 $f (i)$ 表示切片以 v [i] 结尾的 LIS。举个例子：
i 0 1 2 3 4 5
v 4 0 6 1 2 3
f 1 1 2 2 3 4
注意到计算过程为（以 $i=3$ 为例）
f (3) = ? 不知道
注意到最后一个满足 v [3] > v [k] 的 k 是 k = 1
于是 f (3) = f (1) + 1
总结：$f (i) = f (k) + 1$，其中 $k$ 为：满足 $k < i$ 且 $v [k] < v [i]$ 的，最大的 f [k] 所对应的 k
- $k < i$ 是切片约束。
- $v [k] < v [i]$ 是递增约束
- 最大的
f [k]所对应的 k 是最长子序列约束
初始条件：f [0] = 1
参考代码：
class Solution {
public:
int find_k(std::vector<int> &v, std::vector<int> &dp, int i) {
int max_vk = -1;
int find_k = -1;
for (int k = 0; k < i; k++) {
if (v[k] < v[i] && dp[k] > max_vk) {
max_vk = dp[k];
find_k = k;
}
}
return find_k;
}
int lengthOfLIS(vector<int> &v) {
auto n = v.size();
//dp [i] 表示以 v [i] 结尾的 v [0:i] 的 LIS
std::vector<int> dp(n);
dp[0] = 1;
auto llis = 1;
for (int i = 1; i < n; i++) {
auto k = find_k(v, dp, i);
if (k == -1) {
dp[i] = 1;
} else {
dp[i] = dp[k] + 1;
}
printf("dp = ");
print_vec(dp);
llis = max(dp[i], llis);
}
return llis;
}
};
参考代码 2：
class Solution {
public:
int lengthOfLIS(vector<int> &v) {
auto n = v.size();
if (n == 0)
return 0;
std::vector<int> dp(n);
dp[0] = 1;
int llis = 1;
for (int i = 1; i < n; i++) {
dp[i] = 1;
for (int k = 0; k < i; k++) {
if (v[k] < v[i]) {
dp[i] = max(dp[i], dp[k] + 1);
}
}
print_vec(dp);
llis = max(llis, dp[i]);
}
return llis;
}
};
Game of 5 Powers
You are given a string S that consists of characters ‘0’ and ‘1’ only. Return the smallest positive integer K such that it is possible to cut S into K pieces, each of them being a power of 5 (no leading zeros). If there is no such K, return -1 instead.
e.g. S=“101101101" return3 (101 = 5)
e.g. S=“1111101”return 1 (1111101 = 125)
e.g. S =“0000”return -1
e.g. S=“100" return -1
即输入 01 串，我们要将这个串分为几个部分，每个部分都是 $5^n$，返回最小的划分次数。例如 1011111101，可以划分为 101 1111101，所以返回 2.
分析：
为了保证尽量小，我们要让划分中所含的数字尽量大。
i 0 1 2 3 4 ............ n-1
v 1 0 1 0 0 ........... 0 1
我们可以采用插空法，定义 f (i) 为在 i 出分割的最小划分。
举个例子，对于 101101101，空格表示切割位置
i = 0, f (101101101) 可以，因为 101101101 不是 5^n
i = 1, 1 f (01101101) 不行，因为 1 不是 5^n
...
i = 3，101 f (101101) 可以，因为 101 是 5^n
即我们要确保分割的前一部分是 5^n，同时后一部分通过迭代算出。
参考代码：
bool isPowerOf5(string str){
if(str[0] == '0')
return false;
long num = 0;
for (char s : str){
num << 1;
if(s == '1')
num++;
}
while(num % 5 == 0) num/=5;
return num == 1;
}
int solve(string str) {
int n = str.size();
vector<int> dp(n);
fill(dp.begin(), dp.end(), -1);
for (int i = 0; i < n; i++){
if(isPowerOf5(substring(str, 0, i+1))) {
dp[i] = 1;
continue;
}
for (int j = 0; j < i; j++) {
string last = substring(str, j+1, i+1);
if(dp[j] == -1 || !isPowerOf5(last))
continue;
if(dp[i] == -1 || dp[i] > dp[j] + 1){
dp[i] = dp[j] + 1;
}
}
}
return dp[n-1];
}
双序列型 DP
输入序列为两个数组。$f (i,j)$ 表示输入为 $A [0:i], B [0:j]$ 时的状态，建立其与 $f (i-1,j),f (i-1,j-1),f (i,j-2),f (i-2,j),f (i-2,j-1)$ 等所有更小的情况的关系。
LC 1143. 最长公共子序列（LCS）
定义 $f (i,j)$ 表示 A [0:i], B [0:j] 的 LCS。
考虑 A [i] != B [j]，即最后一个字符不相等，那么我们只能拿掉一个字符比较。可以从 A 拿，也可以从 B 拿。即 $f (i,j) = \max \{f (i-1,j),f (i,j-1)\}$.
考虑 A [i] == B [j]，即最后一个匹配，则只要看除去最后一个字符的剩余前面部分是否匹配，即 $f (i,j) = f (i-1,j-1)+1$
然后考虑起始值：$f (0,j) = 0$ $f (i,0) = 0$。据此写代码：
class Solution {
public:
int longestCommonSubsequence(string a, string b) {
auto n = a.size(), m = b.size();
vector<vector<int>>
dp (n + 1,vector<int>(m + 1, 0)); // 注意 dp 数组的大小不是 nxm
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 - 1][j], dp[i][j - 1]);
}
print_vec_2d(dp);
}
}
return dp[n][m];
}
};
下面考虑空间优化。
注意到只依赖 dp [i-1][j-1]，即我们总是关注 2x2 的局部。所以可以对此优化。但是我们无法优化到 $O (1)$，这是因为虽然我们在 b 的循环中只引用了 i-1, j-1，然而 i-1 却是属于上一行的，我们必须保存一整行的数据。其实看计算次序（红箭头画出）就知道：
因此我们必须记忆一整个 a 的行。而 b 相关的可以优化。
参考代码：
class Solution {
public:
int longestCommonSubsequence(string a, string b) {
auto n = a.size(), m = b.size();
auto d = 2;
vector<vector<int>> dp(d,
vector<int>(m + 1, 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 % d][j] = dp[(i - 1) % d][j - 1] + 1;
} else {
dp[i % d][j] = max(dp[(i - 1) % d][j], dp[i % d][j - 1]);
}
}
}
return dp[n % d][m];
}
};
LC 300 最长递增子序列 的新解
我们可以把 A 先排序，然后计算 sortedA 与 A 的 LCS，即为 LIS 解。
LC 718. 最长公共字串
我们从最小情形考虑。举例 A=[12321], B=[32147]，定义 $f (i,j)$ 表示 A [0:i], B [0:j] 的最长公共字串。
考虑 A [i] != B [j]，即最后一个字符不相等，那么可以判定二者不交叉。即 $f (i,j) = 0$.
考虑 A [i] == B [j]，即最后一个匹配，则只要看除去最后一个字符的剩余前面部分是否匹配，即 $f (i,j) = f (i-1,j-1)+1$
我的朴素解法：
class Solution {
public:
int findLength(std::vector<int> &a, std::vector<int> &b) {
auto n = a.size(), m = b.size();
auto d = 2;
int maxval = 0;
vector<vector<int>> dp(d,
vector<int>(m + 1, 0)); // 注意 dp 数组的大小不是 nxm
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a [i - 1] == b [j - 1]) { // 注意下标
dp[i % d][j] = dp[(i - 1) % d][j - 1] + 1;
}
maxval = max(maxval, dp[i % d][j]);
}
}
return maxval;
}
};
但是我发现解并不是 dp [n][m]，而是 dp 数组的最大值。（歪打正着）
老师的解法：
可以定义 $f (i,j)$ 为以 $A [i],B [j]$ 结尾的最长子串。代码就是我上面那样的了。
然后可以进一步空间优化。改成从右往左添加：
class Solution {
public:
int findLength(std::vector<int> &a, std::vector<int> &b) {
int n = a.size(), m = b.size(), maxval = 0;
vector<int> dp(m + 1);
for (int i = 1; i <= n; i++) {
for (int j = m; j > 0; j--) {
if (a [i - 1] == b [j - 1]) { // 注意下标
dp[j] = dp[j - 1] + 1;
maxval = max(maxval, dp[j]);
}else{
dp [j] = 0; // 这句不可少
}
}
}
return maxval;
}
};