前言
更详细的在大佬的代码随想录 (programmercarl.com)
本系列仅是简洁版笔记，为了之后方便观看
做题步骤
含义公式初始化顺序检查
- 确定dp数组以及下标的含义
- 递推公式
- dp数组如何初始化
- 遍历顺序
- 打印dp数组（看哪里有问题）
斐波那契数
class Solution {
public:
int fib(int n) {
if(n<=1) return n;
int dp[2];
dp[0]=0;
dp[1]=1;
for(int i=2;i<=n;i++)
{
int sum = dp[0] + dp[1];
dp[0] = dp[1];
dp[1] = sum;
}
return dp[1];
}
};爬楼梯
70. 爬楼梯 - 力扣（LeetCode）
代码思路和上一题相差不大，主要是初始化和遍历时i的取值不同。
class Solution {
public:
int climbStairs(int n) {
if (n <= 1) return n;
vector<int> dp(n + 1);
dp[1] = 1;//初始化要根据实际情况进行改变
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
};使用最小花费爬楼梯
746. 使用最小花费爬楼梯 - 力扣（LeetCode）
爬楼梯的消费版
dp表示的是到达本层已经使用的体力，cost[i] 是从本台阶向上爬需要支付的费用
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
vector<int> dp(cost.size() + 1);
dp[0] = 0;//根据题意设计
dp[1] = 0;
for (int i = 2; i <= cost.size(); i++) {
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[cost.size()];
}
};不同路径
62. 不同路径 - 力扣（LeetCode）
题意：只能向下向右到目标地点，求路径数
dp[i][j] 只和 dp[i - 1][j] 和dp[i][j - 1]有关，很容易造成的观点错误是dp[i - 1][j]+1和dp[i][j - 1]推导而来，但是要清楚的是本题求得是路径数，dp[i - 1][j] 只能向下走，dp[i][j - 1]只能向右走，所以路径数不变
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>>dp(m,vector<int>(n,0));
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 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];
}
}
return dp[m - 1][n - 1];
}
};不同路径 II
和上一题的不同点：障碍物的出现
代码不同点：遍历顺序添加限制条件，不同路径初始化要改变
没有障碍物的时候才可以正常遍历
if (obstacleGrid[i][j] == 0) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}vector<vector<int>> dp(m, vector<int>(n, 0));
for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;整数拆分
. - 力扣（LeetCode）
拆成若干数使得相乘最大
技巧：拆分成多个近似相等的数
难思考点：遍历顺序
j * (i - j) ：把整数拆分为两个数相乘，
j * dp[i - j]：拆分成两个以及两个以上的个数相乘
for (int i = 3; i <= n ; i++) {
for (int j = 1; j < i - 1; j++) {
dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
}
}class Solution {
public:
int integerBreak(int n) {
vector<int> dp(n + 1);
dp[2] = 1;//dp[0]和dp[1]都是0 因为不需要拆分
for (int i = 3; i <= n ; i++) {
for (int j = 1; j <= i / 2; j++) {
dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));//求取最大值
}
return dp[n];//返回全部遍历后的最大值
}
};不同的二叉搜索树
96. 不同的二叉搜索树 - 力扣（LeetCode）
通过举例子发现重叠子问题
代码很简单，主要是思路问题，知道二叉搜索树的概念，并分别对左右子树进行计算，相乘
class Solution {
public:
int numTrees(int n) {
vector<int>dp(n+1);
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];
}
};01背包
二维01背包
dp[i][j]表示 [0-i]的物品里任意取容量为j的背包的价值
- 不放物品i：dp[i][j]=dp[i - 1][j]
- 放物品i：dp[i][j]=dp[i - 1][j - weight[i]] + value[i]
- 注意：非零下标不管初始化什么值，都不影响最后结果，但是有零下表初始化需要在注意
dp[0][j]，当 j < weight[0]的时候，放不进去，dp[0][j] = 0；当j >= weight[0]时，dp[0][j] =value[0]
vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0)); for (int j = weight[0]; j <= bagweight; j++) { dp[0][j] = value[0]; }二维数组实现的dp01背包for循环可以颠倒
for(int i = 1; i < weight.size(); i++) { // 物品 for(int j = 0; j <= bagweight; j++) { // 背包 if (j < weight[i]) dp[i][j] = dp[i - 1][j]; else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); } }
一维01背包
dp[j]容量为j的背包的价值
- 不放物品i：dp[j]=dp[j]
- 放物品i：dp[j]=dp[j - weight[i]] + value[i]
- 注意：非零下标不管初始化什么值，都不影响最后结果，但是有零下标初始化为非负数的最小值0就可以
vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0)); for (int j = weight[0]; j <= bagweight; j++) { dp[0][j] = value[0]; }一维数组实现的dp01背包for循环不可以颠倒，背包必须倒序输出，这样才能符合每个背包只能使用一次
vector<int> dp(N + 1, 0); for (int i = 0; i < 物品数量; ++i) { for (int j = N; j >= costs[i]; --j) { dp[j] = max(dp[j], dp[j - costs[i]] + values[i]); } }
分割等和子集
416. 分割等和子集 - 力扣（LeetCode）
把数组分割成两个元素和相等的子集，可以弄成01背包问题，每个数只能使用一次，观察是否能把num/2的背包容量给填满
注意：本题重量和价值是统一变量
dp[j] == j 时集合中的子集总和正好可以凑成总和j
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum=0;
vector<int>dp(10001,0);
for(int i=0;i<nums.size();i++){
sum+=nums[i];
}
if(sum%2==1) return false;//说明凑不成两个一样的数
int target=sum/2;
for(int i=0;i<nums.size();i++){
for(int j = target; j >= nums[i]; j--) {
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
if (dp[target] == target) return true;
return false;
}
};最后一块石头的重量II
1049. 最后一块石头的重量 II - 力扣（LeetCode）
两两石头相撞，最终取得最小差值，可以分成两个数量之和相近的堆，来进行计算是上一题的演变，重量和价值是统一变量
target = sum / 2向下取整，所以sum - dp[target] >=dp[target],，所以最终结果就是用大的减去小的
class Solution {
public:
int lastStoneWeightII(vector<int>& nums) {
int sum=0;
vector<int>dp(15001,0);
for(int i=0;i<nums.size();i++){
sum+=nums[i];
}
int target=sum/2;
for(int i=0;i<nums.size();i++){
for(int j = target; j >= nums[i]; j--) {
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
return sum - dp[target] - dp[target];
}
};目标和
494. 目标和 - 力扣（LeetCode）
一个集合分出两个子集，加法left集合和减法right集合
left- right = target。
left + right = sum
right = sum - left
left - (sum - left) = target
left = (target + sum)/2
targe，sum是固定的，所以就可以转化为在集合nums中找出和为left的组合
class targetolution {
public:
int findTargettargetumWays(vector<int>& nums, int target) {
int sum = 0;
for (int i = 0; i < nums.size(); i++) sum += nums[i];
if (abs(target) > sum) return 0;
if ((target + sum) % 2 == 1) return 0;
int bagtargetize = (target + sum) / 2;
vector<int> dp(bagtargetize + 1, 0);
dp[0] = 1;
for (int i = 0; i < nums.size(); i++) {
for (int j = bagtargetize; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]];
}
}
return dp[bagtargetize];
}
};
一和零
474. 一和零 - 力扣（LeetCode）
dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]
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);
}
}完全背包
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]);
}
}零钱兑换II
. - 力扣（LeetCode）
因为纯完全背包不在乎有没有顺序，有顺序也行没有顺序也行，但是这个题目的要求是没有顺序，求组合数，所以就要考虑for循环先后顺序调换有没有影响了
组合情况：先把1加入计算，然后再把5加入计算，得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况
for (int i = 0; i < coins.size(); i++) { // 遍历物品
for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量
dp[j] += dp[j - coins[i]];
}
}排列数情况：背包容量的每一个值，都是经过 1 和 5 的计算，包含了{1, 5} 和 {5, 1}两种情况。
for (int j = 0; j <= amount; j++) { // 遍历背包容量
for (int i = 0; i < coins.size(); i++) { // 遍历物品
if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];
}
}组合总和IV
. - 力扣（LeetCode）
if 语句的作用
确保在执行状态转移时不会访问不合法的索引，防止整数溢出。这是动态规划算法中常见的边界检查和安全性措施。
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<int> 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] < INT_MAX - dp[i - nums[j]]) {
dp[i] += dp[i - nums[j]];
}
}
}
return dp[target];
}
};
零钱和
322. 零钱兑换 - 力扣（LeetCode）
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, INT_MAX);
dp[0] = 0;
for (int i = 0; i < coins.size(); i++) {
for (int j = coins[i]; j <= amount; j++) {
if (dp[j - coins[i]] != INT_MAX) {
dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
}
}
}
if (dp[amount] == INT_MAX) return -1;
return dp[amount];
}
};单词拆分
139. 单词拆分 - 力扣（LeetCode）
要考虑for循环的先后顺序
lass Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
vector<bool> dp(s.size() + 1, false);
dp[0] = true;
for (int j = 0; j < wordDict.size(); j++) { // 物品
for (int i = wordDict[j].size(); i <= s.size(); i++) { // 背包
string word = s.substr(i - wordDict[j].size(), wordDict[j].size());
if ( word == wordDict[j] && dp[i - wordDict[j].size()]) {
dp[i] = true;
}
}
}
return dp[s.size()];
}
};打家劫舍
打家劫舍
相邻房间不能偷，考虑两种情况，偷或者不偷
198. 打家劫舍 - 力扣（LeetCode）
class Solution {
public:
int rob(vector<int>& nums) {
if (nums.size() == 0) return 0;
if (nums.size() == 1) return nums[0];
vector<int> dp(nums.size());
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]);
}
return dp[nums.size() - 1];
}
};打家劫舍II
和上一题不同点：首尾相连连成环
情况如下
- 不考虑首尾元素，首尾元素连成环无影响
- 考虑首元素，默认没有尾元素，但头元素可选可不选
- 考虑尾元素，默认没有首元素，但尾元素可选可不选
情况2,3包含了情况1，所以分成两种情况，分别取两种情况的最大值
class Solution {
public:
int rob(vector<int>& nums) {
if (nums.size() == 0) return 0;
if (nums.size() == 1) return nums[0];
int result1 = robRange(nums, 0, nums.size() - 2);
int result2 = robRange(nums, 1, nums.size() - 1);
return max(result1, result2);
}
int robRange(vector<int>& nums, int start, int end) {
if (end == start) return nums[start];
vector<int> dp(nums.size());
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 - 2] + nums[i], dp[i - 1]);
}
return dp[end];
}
};打家劫舍III
337. 打家劫舍 III - 力扣（LeetCode）
遍历方式：后序遍历
与前两题的不同点是这个是在二叉树的结构当中
class Solution {
public:
int rob(TreeNode* root) {
vector<int> result = robTree(root);
return max(result[0], result[1]);//根节点投或者不投
}
// 长度为2的数组，0：不偷，1：偷
vector<int> robTree(TreeNode* cur) {
if (cur == NULL) 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};
}
};买卖股票的最佳时机
买卖股票的最佳时机1
dp[i][0] ：第i天持有股票所得最多现金
dp[i][1] ：第i天不持有股票所得最多现金
dp[i][0] = max(dp[i - 1][0], -prices[i]);
//第i-1天持有股票和第i天买入股票，这里可以看成是纯利润
dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
//第i-1天就不持有股票/第i天出了股票
最后取得最大值的情况坑定是卖出股票的情况，也就是不持有股票的情况
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len=prices.size();
if(len==0) return 0;
vector<vector<int>>dp(len,vector<int>(2));
dp[0][0]-=prices[0];
dp[0][1]=0;
for(int i=1;i<len;i++){
dp[i][0] = max(dp[i - 1][0], -prices[i]);
dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
}
return dp[len - 1][1];
}
};买卖股票的最佳时机II
122. 买卖股票的最佳时机 II - 力扣（LeetCode）
与上题的区别就是可以买卖多次，dp[i][0]递归方式有所变化
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len=prices.size();
if(len==0) return 0;
vector<vector<int>>dp(len,vector<int>(2));
dp[0][0]-=prices[0];
dp[0][1]=0;
for(int i=1;i<len;i++){
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
}
return dp[len - 1][1];
}
};买卖股票的最佳时机III
123. 买卖股票的最佳时机 III - 力扣（LeetCode）
与上两题的区别就是至多可以买卖两次，要分多种情况讨论
多情况讨论
- 无操作
- 第一次持有股票
- 第一次不持有股票
- 第二次持有股票
- 第二次不持有股票
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.size() == 0) return 0;
vector<vector<int>> dp(prices.size(), vector<int>(5, 0));
dp[0][1] = -prices[0];
dp[0][3] = -prices[0];
for (int i = 1; i < prices.size(); i++) {
dp[i][0] = dp[i - 1][0];
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]);
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
}
return dp[prices.size() - 1][4];
}
};买卖股票的最佳时机IV
188. 买卖股票的最佳时机 IV - 力扣（LeetCode）
与上两题的区别就是至多可以买卖K次，要分多种情况讨论
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if (prices.size() == 0) return 0;
vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0));
for (int j = 1; j < 2 * k; j += 2) {
dp[0][j] = -prices[0];
}
for (int i = 1;i < prices.size(); i++) {
for (int j = 0; j < 2 * k - 1; j += 2) {
dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
}
}
return dp[prices.size() - 1][2 * k];
}
};买卖股票的最佳时机含冷冻期
多情况
- 状态一：持有股票状态dp[i][0]
- 不持有股票状态，这里就有两种卖出股票状态
- 状态二：保持卖出股票的状态（前一天/两天卖出股票，没操作/度过一天冷冻期。dp[i][1]）
- 状态三：今天卖出的股票dp[i][2]
- 状态四：冷冻期状态dp[i][3]
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if (n == 0) return 0;
vector<vector<int>> dp(n, vector<int>(4, 0));
dp[0][0] -= prices[0];
for (int i = 1; i < n; i++) {
dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]));
dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
dp[i][2] = dp[i - 1][0] + prices[i];
dp[i][3] = dp[i - 1][2];
}
return max(dp[n - 1][3], max(dp[n - 1][1], dp[n - 1][2]));
}
};买卖股票的最佳时机含手续费
和买卖股票的最佳时机II的区别就是有个手续费
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(2, 0));
dp[0][0] -= prices[0];
for (int i = 1; i < n; i++) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
}
return max(dp[n - 1][0], dp[n - 1][1]);
}
};子序列问题
最长递增子序列
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if (nums.size() <= 1) return nums.size();
vector<int> dp(nums.size(), 1);
int result = 0;
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);//长度要加1
}
if (dp[i] > result) result = dp[i];
}
return result;
}
};最长连续递增序列
674. 最长连续递增序列 - 力扣（LeetCode）
重点在连续
for (int i = 1; i < nums.size(); i++) {
if (nums[i] > nums[i - 1]) {
dp[i] = dp[i - 1] + 1;
}
if (dp[i] > result) result = dp[i];
}
最长重复子数组
dp[i][j] ：以下标i - 1为尾的nums1，和以j - 1为尾的nums的最长重复子数组长度
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
vector<vector<int>> dp (nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
int result = 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;
}
if (dp[i][j] > result) result = dp[i][j];
}
}
return result;
}
};最长公共子序列
dp[i][j]：在区间[0, i - 1]的num1和区间[0, j - 1]的num2的最长公共子序列长度
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
for (int i = 1; i <= text1.size(); i++) {
for (int j = 1; j <= text2.size(); j++) {
if (text1[i - 1] == text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[text1.size()][text2.size()];
}
};不相交的线
1035. 不相交的线 - 力扣（LeetCode）
本质上就是找最长公共子序列
最大子序和
53. 最大子数组和 - 力扣（LeetCode）
dp[i]：以i结尾的（nums[i]）的最大连续子序列和
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if (nums.size() == 0) return 0;
vector<int> dp(nums.size());
dp[0] = nums[0];
int result = dp[0];
for (int i = 1; i < nums.size(); i++) {
dp[i] = max(dp[i - 1] + nums[i], nums[i]);
if (dp[i] > result) result = dp[i];
}
return result;
}
};编辑距离
判断子序列
392. 判断子序列 - 力扣（LeetCode）
s和t的最长公共子序列长度就等于最短的那个子序列的长度，就说明s是t的子序列
class Solution {
public:
bool isSubsequence(string s, string t) {
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;
}
};不同的子序列
115. 不同的子序列 - 力扣（LeetCode）
递归顺序
原因可以看例子：因为考虑的是从s中删除元素会不会和t相等，所以如果s=“bagg”，t=“bag”，则t可以有s[0][1][2]和s[0][1][3]组成
if (s[i - 1] == t[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j];
}这里初始化有所变化，因为如果s中有元素，t中没元素的话就是有一个方案，如果t中有元素，s中没有元素方案个数为0
代码
class Solution {
public:
int numDistinct(string s, string t) {
vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1));
for (int i = 0; i < s.size(); i++) dp[i][0] = 1;
for (int j = 1; j < t.size(); j++) dp[0][j] = 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] + dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[s.size()][t.size()];
}
};两个字符串的删除操作
删除两个字符串的元素，使两个字符串相同
dp[i][j]：以i-1为尾的字符串word1和以j-1为尾的字符串word2相同的最小操作次数
class Solution {
public:
int minDistance(string word1, string word2) {
vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));
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 {
dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
}
}
}
return dp[word1.size()][word2.size()];
}
};
编辑距离
72. 编辑距离 - 力扣（LeetCode）
让word1变成word2，通过增删改
dp[i][j]：以i-1为尾的字符串word1和以j-1为尾的字符串word2相同的最小操作次数
理解：删除word1中的元素相当于添加word2中的元素
改的操作就相当于 dp[i][j] = dp[i - 1][j - 1] + 1;
class Solution {
public:
int minDistance(string word1, string word2) {
vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
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 {
dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
}
}
}
return dp[word1.size()][word2.size()];
}
}回文子串
647. 回文子串 - 力扣（LeetCode）
class Solution {
public:
int countSubstrings(string s) {
vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
int result = 0;
for (int i = s.size() - 1; i >= 0; i--) {
for (int j = i; j < s.size(); j++) {
if (s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1])) {
result++;
dp[i][j] = true;
}
}
}
return result;
}
};最长回文子序列
516. 最长回文子序列 - 力扣（LeetCode）
和上一题的最大区别是该题不强调连续性
注意i的遍历顺序，i是从下向上遍历的
注意for循环不可以颠倒，因为j是依赖于i的大小的
class Solution {
public:
int longestPalindromeSubseq(string s) {
vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
for (int i = 0; i < s.size(); i++) dp[i][i] = 1;
for (int i = s.size() - 1; i >= 0; i--) {
for (int j = i + 1; j < s.size(); j++) {
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][s.size() - 1];
}
};
