More content：LeetCode hot100@动态规划&多维动态规划
DP是由前一个状态推导而出，而贪心是在局部直接选择最优
DP五部曲：
- 确定dp数组以及下标的含义
- 确定递推公式(状态转移公式)
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
01背包模板：
for(int i = 0; i < weight.size(); i++) { //遍历物品
for(int j = bagWeight; j >= weight[i]; j--) { //遍历背包容量(为了确保每个物品最多被添加一次，所以要从大到小去遍历)
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); //求背包容纳的最大价值(添加,不添加)
dp[j] += dp[j - nums[i]]; //求装满背包的不同组合数
//cout << "i = " << i << ", j = " << j << ", dp[" << j << "] = " << dp[j] << endl;
}
}完全背包模板：
//常规模板
for(int i = 0; i < weight.size(); i++) { //遍历物品
for(int j = weight[i]; j <= bagWeight; j++) { //遍历背包容量(每个物品都可以多次添加，因此从小到大去遍历)
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); //添加or不添加
//cout << "i = " << i << ", j = " << j << ", dp[" << j << "] = " << dp[j] << endl;
}
}
//求组合种数
for(int i = 0; i < nums.size(); i++) { //遍历物品
for(int j = nums[i]; j <= bagWeight; j++) { //遍历背包容量
dp[j] += dp[j - nums[i]]; //求装满背包的不同组合数
}
}
//求排列种数
for(int i = 0; i <= bagWeight; i++) { //先遍历背包容量
for(int j = 0; j < nums.size(); j++) { //再遍历物品
if(i - nums[j] >= 0) dp[i] += dp[i - nums[j]]; //求装满背包的不同排列数
}
}ps：DP的一些题目也能用递归回溯搜索，但往往会超时，毕竟类似于暴力
刷题大纲
- 基础题目
- 背包问题
- 打家劫舍问题
- 股票问题
- 只能买卖一次121. 买卖股票的最佳时机
- 可以买卖多次122. 买卖股票的最佳时机 II
- 最多买卖两次123. 买卖股票的最佳时机 III
- 最多买卖k次188. 买卖股票的最佳时机 IV
- 买卖多次，卖出有一天冷却期309. 买卖股票的最佳时机含冷冻期
- 买卖多次，每次都有手续费714. 买卖股票的最佳时机含手续费
- 子序列问题
- 子序列(不连续)
- 子序列(连续)
- 编辑距离
- 回文
基础题目
62. 不同路径✅
Solution1：递归回溯搜索（一开始超内存，后精简变量，但超时，只能过样例，遂放弃）（原因：回溯搜索本质上是暴力）
Solution2：动态规划（详见注释）
class Solution1 {
private:
// vector<string> res; //其实只定义一个变量来记录方案数就可以
// string path; //这样定义变量是为了方便debug
int res;
vector<vector<int>> map;
public:
void backTracking(int row, int col, int m, int n) {
if(row == m-1 && col == n-1) {
// res.push_back(path);
res++;
return ;
}
//搜题目给的两个方向
if(row != m-1 && !map[row+1][col]) { //下
map[row+1][col] = 1;
// path += "D";
backTracking(row+1, col, m, n);
map[row+1][col] = 0;
// path.erase(path.size()-1, 1);
}
if(col != n-1 && !map[row][col+1]) { //右
map[row][col+1] = 1;
// path += "R";
backTracking(row, col+1, m, n);
map[row][col+1] = 0;
// path.erase(path.size()-1, 1);
}
//最后返回
return ;
}
int uniquePaths(int m, int n) {
map = vector<vector<int>>(m, vector<int>(n, 0));
map[0][0] = 1;
res = 0;
backTracking(0, 0, m, n);
// for(const auto &i : res) cout << i << endl;
// return res.size();
return res;
}
};class Solution2 {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m, vector<int>(n, 0)); //表示走到坐标为(i, j)的位置有dp[i][j]种不同路径
//初始化
for(int i = 0; i < m; i++) dp[i][0] = 1;
for(int i = 0; i < n; i++) dp[0][i] = 1;
for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
dp[i][j] = dp[i-1][j] + dp[i][j-1]; //要不从上一格过来 要不从左一格过来
cout << "dp[" << i << "][" << j << "] = " << dp[i][j] << endl;
}
}
return dp[m-1][n-1];
}
};63. 不同路径 II✅
搜索会超时，依然动态规划
与上题类似，只是初始化复杂一点，再把障碍位置的dp[i][j]设为0即可
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0)); //表示走到坐标为(i, j)的位置有dp[i][j]种不同路径
//初始化
int firstCol_pos = m;
int firstRow_pos = n;
for(int i = 0; i < m; i++) { //寻找第一列的第一个障碍位置
if(obstacleGrid[i][0]) {
firstCol_pos = i;
break;
}
}
for(int i = 0; i < n; i++) { //寻找第一行的第一个障碍位置
if(obstacleGrid[0][i]) {
firstRow_pos = i;
break;
}
}
for(int i = 0; i < firstCol_pos; i++) dp[i][0] = 1;
for(int i = 0; i < firstRow_pos; i++) dp[0][i] = 1;
for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
if(obstacleGrid[i][j]) dp[i][j] = 0;
else dp[i][j] = dp[i-1][j] + dp[i][j-1]; //要不从上一格过来 要不从左一格过来
cout << "dp[" << i << "][" << j << "] = " << dp[i][j] << endl;
}
}
return dp[m-1][n-1];
}
};70. 爬楼梯✅
dp数组下标代表当前在第几阶，数组value表示到这一阶的方法数（即爬到第i层楼梯，有dp[i]种方法）
遍历顺序从前往后 但是一开始没想明白为什么状态转移公式是dp[i] = dp[i-1] + dp[i-2] 只是找规律推出来的
class Solution {
public:
int climbStairs(int n) {
vector<int> dp(50); //dp数组下标代表当前在第几阶，数组value表示到这一阶的方法数
dp[1] = 1;
dp[2] = 2;
if(n < 3) return dp[n];
for(int i = 3; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
return dp[n];
}
};96. 不同的二叉搜索树❌
想不出状态转移公式
class Solution {
public:
int numTrees(int n) {
vector<int> dp(n + 1); //表示i个节点组成的不相同BST有dp[i]种
/*
dp[0] =
dp[1] = 1
dp[2] = 2
dp[3] = 5
*/
dp[0] = 1;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= i; j++) {
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
};343. 整数拆分❌
Solution1：第一反应是回溯搜索，不出所料超时了，只能过样例
Solution2：DP（详见注释）
class Solution1 {
private:
int res = 0;
int mul = 1;
public:
void backTracking(int n, int depth) {
// if(n < 0) return ;
if(!n) {
res = max(res, mul);
cout << "mul = " << mul << endl;
return ;
}
//第一层不能取到n 因为0*n为0
for(int i = 1; i <= n; i++) {
if(depth == 1 && i == n) continue;
mul *= i;
backTracking(n - i, depth + 1);
mul /= i;
}
}
int integerBreak(int n) {
backTracking(n, 1);
return res;
}
};class Solution2 {
public:
int integerBreak(int n) {
vector<int> dp(n + 1); //表示n为i时的最大乘积是dp[i]
dp[2] = 1;
// dp[3] = 2;
// dp[4] = 4
for(int i = 3; i <= n; i++) {
for(int j = 1; j < i; j++) {
//对于遍历的j，要么把i拆分为两份，要么继续往前拆
//即j是拆分i的第一个数
dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
}
}
return dp[n];
}
};509. 斐波那契数✅
状态转移公式给了，初始化给了，遍历从前往后即可
class Solution {
public:
int fib(int n) {
int f[35];
f[0] = 0;
f[1] = 1;
for(int i = 2; i <= n; i++) f[i] = f[i-1] + f[i-2];
return f[n];
}
};746. 使用最小花费爬楼梯✅
爬上第i阶楼梯的最小费用为dp[i]
状态转移公式为dp[i] = min(cost[i-1] + dp[i-1], cost[i-2] + dp[i-2]) 因为要不从上一阶爬上来，要不从上两阶爬上来，只要支付了当时那阶的费用即可，因此从两种选择中找花费较小的
初始化： dp[0] = 0; dp[1] = 0;
遍历顺序从前往后
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
vector<int> dp(1005); //爬上第i阶楼梯的最小费用为dp[i]
dp[0] = 0;
dp[1] = 0;
for(int i = 2 ; i <= cost.size(); i++) {
dp[i] = min(cost[i-1] + dp[i-1], cost[i-2] + dp[i-2]);
cout << "i = " << i << ", dp[i] = " << dp[i] << endl;
}
return dp[cost.size()];
}
};背包问题
416. 分割等和子集✅
01背包应用题：一个元素只能选一次，重量数组和价值数组相同，如果能用集合中的元素正好填满容量为sum/2的背包，即dp[j] = j，则返回true
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for(const auto &i : nums) sum += i;
if(sum % 2) return false;
sum /= 2;
vector<int> dp(sum + 1);
dp[0] = 0;
for(int i = 0; i < nums.size(); i++) {
for(int j = sum; j >= nums[i]; j--) {
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
if(i == nums.size()-1) cout << "dp[" << j << "] = " << dp[j] << endl;
}
}
if(dp[sum] == sum) return true;
else return false;
}
};474. 一和零❌
两个维度的01背包
最多有i个0和j个1的strs的最大子集的大小为dp[i][j]
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0));
for(const auto &str : strs) { //遍历物品
int oneNum = 0, zeroNum = 0;
for(const auto &c : str) {
if(c == '0') zeroNum++;
else oneNum++;
}
for(int i = m; i >= zeroNum; i--) { //遍历背包容量且从后向前遍历
for(int j = n; j >= oneNum; j--) {
dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
// cout << "str = " << str << " dp[" << i << "][" << j << "] = " << dp[i][j] << endl;
}
}
}
return dp[m][n];
}
};494. 目标和❌
不是求背包里最多能装多少了，而是背包装满有多少种方法
详见题解：https://programmercarl.com/0494.%E7%9B%AE%E6%A0%87%E5%92%8C.html#%E6%80%9D%E8%B7%AF
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sum = 0;
for(const auto &i : nums) sum += i;
int bag = (target + sum) / 2;
if((target + sum) % 2 == 1) return 0;
if(abs(target) > sum) return 0;
vector<int> dp(bag + 1, 0);
dp[0] = 1;
for(int i = 0; i < nums.size(); i++) {
for(int j = bag; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]];
}
}
return dp[bag];
}
};1049. 最后一块石头的重量 II❌
不知道怎么应用到01背包
石头的重量和价值等同，dp[j]表示当背包容量为j时所能容纳的石头总重量，把背包容量定为sum/2，则一堆石头和另一堆石头的重量分别是dp[sum/2]和sum – dp[sum/2]
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int sum = 0;
for(const auto &i : stones) sum += i;
int bag = sum / 2;
cout << "sum = " << sum << endl;
vector<int> dp(bag+1, 0);
for(int i = 0; i < stones.size(); i++) {
for(int j = bag; j >= stones[i]; j--) {
dp[j] = max(dp[j], dp[j-stones[i]] + stones[i]);
if(i == stones.size() - 1) cout << "dp[" << j << "] = " << dp[j] << endl;
}
}
return sum - dp[bag] - dp[bag];
}
};57. 爬楼梯（第八期模拟笔试）✅
跟377. 组合总和 Ⅳ同理，一次迈一阶、两阶、n阶看做是不同的物品，每个物品可以取多次，最后求排列数
139. 单词拆分✅
单词可以重复使用 想到完全背包
数组含义：拼出目标字符串前i个字符所需要的最少单词数为dp[i]
为了能多次选到重复的单词（本质上是排列问题：aba和aab不同），因此必须先遍历背包容量，再遍历物品
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
vector<uint64_t> dp(s.size() + 1, INT_MAX);
dp[0] = 0;
for(int i = 0; i <= s.size(); i++) {
for(int j = 0; j < wordDict.size(); j++) {
if(i < wordDict[j].size()) continue;
if(s.substr(i - wordDict[j].size(), wordDict[j].size()) == wordDict[j]) {
dp[i] = min(dp[i], dp[i - wordDict[j].size()] + 1);
}
// cout << "i = " << i << ", j = " << j << ", dp[" << j << "] = " << dp[j] << endl;
}
}
if(dp[s.size()] == INT_MAX) return false;
return true;
}
};279. 完全平方数✅
每个完全平方数都可以重复用 想到完全背包
求最少数量 跟322. 零钱兑换很相似 只需要把物品从硬币换成完全平方数即可
class Solution {
public:
int numSquares(int n) {
//当n为i时，凑满n需要的最少完全平方数为dp[i]
vector<int> dp(n + 1, INT_MAX);
dp[0] = 0;
//因为1 <= n <= 10000，值不大，因此可以事先准备一个完全平方数数组
vector<int> nums;
for(int i = 1; i * i <= n; i++) nums.push_back(i * i);
for(int i = 0; i < nums.size(); i++) {
for(int j = nums[i]; j <= n; j++) {
dp[j] = min(dp[j], dp[j - nums[i]] + 1);
}
}
return dp[n];
}
};322. 零钱兑换❌
关键词：每种硬币数量无限 想到完全背包 但是要变式
当总金额为i时，凑满总金额需要的最少硬币个数为dp[i]
dp数组定义 递推公式 dp[0]初始化都对了 但是dp其他元素的初始化错了 应该是一个最大的数
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<uint64_t> dp(amount + 1, INT_MAX);
dp[0] = 0;
for(int i = 0; i < coins.size(); i++) {
for(int j = coins[i]; j <= amount; j++) {
dp[j] = min(dp[j], dp[j - coins[i]] + 1);
// cout << "i = " << i << ", j = " << j << ", dp[" << j << "] = " << dp[j] << endl;
}
}
if(dp[amount] == INT_MAX) return -1;
return dp[amount];
}
};377. 组合总和 Ⅳ❌
之前的组合总和123都能用回溯搜索处理 但这个会超时 因此动态规划
每个元素都可以取无数次 而且最终求的是排列种数 因此直接套完全背包求排列种数模板
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<uint64_t> dp(target + 1, 0);
dp[0] = 1;
for(int i = 0; i <= target; i++) {
for(int j = 0; j < nums.size(); j++) {
if(i - nums[j] >= 0) dp[i] += dp[i - nums[j]];
}
}
return dp[target];
}
};518. 零钱兑换 II✅
完全背包问题：硬币的weight等同value，当背包容量为i时，装满背包的不同组合数为dp[i]
uint64_t表示64位无符号整型
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<uint64_t> dp(amount + 1, 0); //无符号64位整型
dp[0] = 1;
for(int i = 0; i < coins.size(); i++) {
for(int j = coins[i]; j <= amount; j++) {
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
};打家劫舍
198. 打家劫舍❌
dp数组含义：前i间房屋能偷的最高金额为dp[i]
初始化：dp[0]=nums[0]（下标为0也就是第一间房屋，能偷的最高金额自然为nums[0]），dp[1] = max(nums[0], nums[1])（相邻的两间房只能偷一个，因此哪个金额高就偷哪个）
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size() == 1) return nums[0];
vector<uint64_t> dp(nums.size() + 1, 0);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for(int i = 2; i < nums.size(); i++) {
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]); //第i家偷or不偷
// cout << "dp[" << i << "] = " << dp[i] << endl;
}
return dp[nums.size()-1];
}
};213. 打家劫舍 II❌
不知道怎么初始化dp数组
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size() == 1) return nums[0];
return max(robRange(0, nums.size() - 2, nums), robRange(1, nums.size() - 1, nums));
}
int robRange(int start, int end, vector<int>& nums) {
if(start == end) return nums[start];
vector<int> dp(nums.size() + 1, 0);
dp[start] = nums[start];
dp[start+1] = max(nums[start], nums[start+1]);
for(int i = start + 2; i <= end; i++) {
dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
}
return dp[end];
}
};337. 打家劫舍 III❌
简单地想成了层序遍历，以层为单位偷，但实际上在一层中可以偷其中几个，而不是全偷或全不偷
树形DP 需要递归后序遍历 使用一个长度为2的数组，记录当前节点偷与不偷所得到的的最大金钱
class Solution {
public:
int rob(TreeNode* root) {
vector<int> res = robTree(root);
return max(res[0], res[1]);
}
//长度为2的数组：下标0代表不偷 1代表偷
vector<int> robTree(TreeNode* cur) {
if(!cur) return vector<int>{0, 0};
vector<int> left = robTree(cur->left);
vector<int> right = robTree(cur->right);
//偷cur 那么就不能偷左右节点
int val1 = cur->val + left[0] + right[0];
//不偷cur 那么可以偷也可以不偷左右节点 取较大的情况
int val2 = max(left[0], left[1]) + max(right[0], right[1]);
return {val2, val1};
}
};股票问题
121. 买卖股票的最佳时机❌
只能买卖一次
Solution1：贪心 遍历维护左边最小值与右边最大值
Solution2：DP 不会定义此类题的数组含义
数组含义：dp[i][0] 表示第i天持有股票所得最多现金 dp[i][1] 表示第i天不持有股票所得最多现金
递推公式：
- dp[i][0] = max(dp[i-1][0], – prices[i]); //i-1天的时候就已经持有 or 第i天买入
- dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]); //i-1天的时候就已经不持有 or 第i天卖出
class Solution1 {
public:
int maxProfit(vector<int>& prices) {
int low = INT_MAX;
int res = 0;
for(int i = 0; i < prices.size(); i++) {
low = min(low, prices[i]);
res = max(res, prices[i] - low);
}
return res;
}
};class Solution2 {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size() + 1, vector<int>(2, 0));
//dp[i][0] 表示第i天持有股票所得最多现金
//dp[i][1] 表示第i天不持有股票所得最多现金
dp[0][0] = 0 - prices[0];
dp[0][1] = 0;
cout << "dp[0][0] = " << dp[0][0] << " dp[0][1] = " << dp[0][1] << endl;
for(int i = 1; i < prices.size(); i++) {
dp[i][0] = max(dp[i-1][0], - prices[i]); //i-1天的时候就已经持有 or 第i天买入
dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]); //i-1天的时候就已经不持有 or 第i天卖出
// cout << "dp[" << i << "][0] = " << dp[i][0] << " dp[" << i << "][1] = " << dp[i][1] << endl;
}
return dp[prices.size()-1][1];
}
};122. 买卖股票的最佳时机 II✅
可以买卖任意次
Solution1：贪心（只要后一天比当前价高，就买了再卖）
Solution1：DP（类似上题，但注意在dp[i][0]的递推公式上略有不同，因为上题只能买卖一次，没积累现金）
class Solution1 {
public:
int maxProfit(vector<int>& prices) {
int res = 0;
if(prices.size() == 1) return 0;
for(int i = 0; i < prices.size() - 1; i++) {
if(prices[i] < prices[i+1]) {
res += prices[i+1] - prices[i];
}
}
return res;
}
};class Solution2 {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size()+1, vector<int>(2, 0));
//dp[i][0]表示第i天持有股票所得最多现金
//dp[i][1]表示第i天不持有股票所得最多现金
dp[0][0] = -prices[0];
dp[0][1] = 0;
for(int i = 1; i < prices.size(); i++) {
//i-1天的时候就已经持有 or 第i天买入（与上题有差异，因为上题没有积累现金）
dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]);
//i-1天的时候就已经不持有 or 第i天卖出
dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);
}
return dp[prices.size()-1][1];
}
};123. 买卖股票的最佳时机 III❌
难点在于最多买卖两次，因此dp[i][0]、dp[i][1]两个状态不够了
dp数组含义：i表示第i天，j为0~3四个状态，dp[i][j]表示第i天状态j所剩最大现金
- 第一次持有股票
- 第一次不持有股票
- 第二次持有股票
- 第二次不持有股票
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size()+1, vector<int>(4, 0));
//i表示第i天，j为0~3四个状态，dp[i][j]表示第i天状态j所剩最大现金
//状态0表示第一次持有股票
//状态1表示第一次不持有股票
//状态2表示第二次持有股票
//状态3表示第二次不持有股票
dp[0][0] = -prices[0];
dp[0][2] = -prices[0];
for(int i = 1; i < prices.size(); i++) {
dp[i][0] = max(dp[i-1][0], -prices[i]);
dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);
dp[i][2] = max(dp[i-1][2], dp[i-1][1] - prices[i]);
dp[i][3] = max(dp[i-1][3], dp[i-1][2] + prices[i]);
}
return dp[prices.size()-1][3];
}
};188. 买卖股票的最佳时机 IV
309. 买卖股票的最佳时机含冷冻期
714. 买卖股票的最佳时机含手续费
子序列问题
300. 最长递增子序列❌
dp数组含义：dp[i]表示i之前(包括i)以nums[i]结尾的最长递增子序列的长度
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int res = 1;
vector<int> dp(nums.size()+1, 1); //下标从0到i的元素的最长递增子序列长度为dp[i]
for(int i = 1; i < nums.size(); i++) {
for(int j = 0; j < i; j++) {
if(nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
res = max(res, dp[i]);
}
return res;
}
};1035. 不相交的线
1143. 最长公共子序列
53. 最大子数组和
674. 最长连续递增序列✅
求最长的连续递增子序列，自然想到滑动窗口
但是DP更简单，相当于300. 最长递增子序列的简单版
也可以用贪心，更简单
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
int res = 1;
vector<int> dp(nums.size()+1, 1); //以下标i的元素结尾的最长递增序列长度为dp[i]
for(int i = 1; i < nums.size(); i++) {
if(nums[i] > nums[i-1]) {
dp[i] = dp[i-1] + 1;
}
cout << "dp[" << i << "] = " << dp[i] << endl;
res = max(res, dp[i]);
}
return res;
}
};718. 最长重复子数组❌
用二维数组记录两个字符串的所有比较情况
dp数组含义：以下标i – 1为结尾的A，和以下标j – 1为结尾的B，最长重复子数组长度为dp[i][j]
ps：为什么用i-1而不是i？这样dp[i][0] 和dp[0][j]都没有意义，直接初始化为0，而不用额外初始化
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
//以下标i-1为结尾的A，和以下标j-1为结尾的B，最长重复子数组长度为dp[i][j]
vector<vector<int>> dp(nums1.size()+1, vector<int>(nums2.size()+1, 0));
int res = 0;
for(int i = 1; i <= nums1.size(); i++) {
for(int j = 1; j <= nums2.size(); j++) {
if(nums1[i-1] == nums2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
}
// cout << "dp[" << i << "][" << j << "] = " << dp[i][j] << endl;
res = max(res, dp[i][j]);
}
}
return res;
}
};※72. 编辑距离❌
dp数组含义：以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]
或者可以换个说法：word1中前i个字母组成的字符串，和word2中前j个字母组成的字符串，最近编辑距离为dp[i][j]（因为比如word=”abc”，当i=2时，即代表以下标i-1为结尾的字符串“ab”，也就是前i个字母）
初始化：dp[i][0]：以下标i-1为结尾的字符串word1，和空字符串word2，最近编辑距离为dp[i][0]，即i；dp[0][j]同理
class Solution {
public:
int minDistance(string word1, string word2) {
//以下标i-1为结尾的字符串word1,和以下标j-1为结尾的字符串word2,最近编辑距离为dp[i][j]
//即word1中前i个字母组成的字符串，和word2中前j个字母组成的字符串，最近编辑距离为dp[i][j]
vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1, 0));
//dp[i][0]：以下标i-1为结尾的字符串word1,和空字符串word2,最近编辑距离为dp[i][0],即i
for(int i = 0; i <= word1.size(); i++) dp[i][0] = i;
for(int j = 0; j <= word2.size(); j++) dp[0][j] = j;
for(int i = 1; i <= word1.size(); i++) {
for(int j = 1; j <= word2.size(); j++) {
if(word1[i-1] == word2[j-1]) {
dp[i][j] = dp[i-1][j-1];
} else {
//word1删除一个元素 or word2删除一个元素 or 替换一个元素
dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
}
}
}
return dp[word1.size()][word2.size()];
}
};115. 不同的子序列
392. 判断子序列✅
Solution1：简单循环判断（本质双指针）
Solution2：看成编辑距离的简化版，只需要计算删除的情况，不用考虑增加和替换
dp数组含义：以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]
class Solution1 {
public:
bool isSubsequence(string s, string t) {
if(s.size() == 0) return true;
if(t.size() == 0) return false;
int k = 0;
for(int i = 0; i < t.size(); i++) {
if(t[i] == s[k]) k++;
if(k == s.size()) return true;
}
return false;
}
};class Solution2 {
public:
bool isSubsequence(string s, string t) {
//以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]
vector<vector<int>> dp(s.size()+1, vector<int>(t.size()+1, 0));
for(int i = 1; i <= s.size(); i++) {
for(int j = 1; j <= t.size(); j++) {
if(s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = dp[i][j-1];
}
}
if(dp[s.size()][t.size()] == s.size()) return true;
return false;
}
};583. 两个字符串的删除操作
516. 最长回文子序列
647. 回文子串❌
Solution1：DP
dp数组含义：表示区间范围[i,j]的子串是否是回文子串，如果是，则dp[i][j]为true，否则为false
遍历顺序：从下到上，从左到右（详见代码随想录）
Solution2：双指针
遍历中心点的，注意中心点有两种情况：一个元素可以作为中心点，两个元素也可以作为中心点
class Solution1 {
public:
int countSubstrings(string s) {
vector<vector<bool>> dp(s.size() + 1, vector<bool>(s.size() + 1, false));
int cnt = 0;
for(int i = s.size() - 1; i >= 0; i--) {
for(int j = i; j < s.size(); j++) {
if(s[i] == s[j]) {
if(j - i <= 1) {
dp[i][j] = true;
cnt++;
} else if(dp[i+1][j-1]){
dp[i][j] = true;
cnt++;
}
}
}
}
return cnt;
}
};class Solution2 {
private:
int extend(string &s, int l, int r) {
int num = 0;
while(l >= 0 && r < s.size() && s[l] == s[r]) {
num++;
l--;
r++;
}
return num;
}
public:
int countSubstrings(string s) {
int cnt = 0;
for(int i = 0; i < s.size(); i++) {
cnt += extend(s, i, i); //以一个元素为中心点
cnt += extend(s, i, i + 1); //以两个元素为中心点
}
return cnt;
}
};