leetcode_动态规划

基础题目

509.斐波那契数

class Solution {
public:
    int fib(int n) {
       if(n==0) return 0;
       vector<int> dp(n+1,0);
       dp[0] = 0;
       dp[1] = 1;
       for(int i =2;i<n+1;i++){
           dp[i] = dp[i-1]+dp[i-2];
       }
       return dp[n];
    }
};

70.爬楼梯

class Solution {
public:
    int climbStairs(int n) {
        if(n==1) return 1;
        vector<int> dp(n+1,0);
        dp[1] = 1;
        dp[2] = 2;
        for(int i =3;i<=n;i++){
            dp[i] = dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
};

62.不同路径

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int> > dp(m,vector<int>(n,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];
    }
};

63.不同路径II

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));
        for(int i =0;i<n;i++){
            if(obstacleGrid[0][i]!=1)
                dp[0][i]=1;
            else break;
        }
        for(int i=0;i<m;i++){
            if(obstacleGrid[i][0]!=1)
                dp[i][0]=1;
            else break;
        }
        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];
                if(obstacleGrid[i][j]==1) dp[i][j]=0;
            }
        }
        return dp[m-1][n-1];
    }
};

343.整数拆分

整数拆分过程中我的递归数组写成了max(dp[i], max(j * (i - j), dp[j] * dp[i - j])),但正确的应该是dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j))
因为j * dp[i - j]是拆分成两个以及两个以上的个数相乘，而dp[i - j] * dp[j] 是默认将一个数强制拆成4份以及4份以上了，少算了。

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1, 0);
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            for (int j = 2; j <= i/2+1; j++) {
                dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
};

96. 不同的二叉搜索树

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n+1,0);
        dp[1] = 1;
        dp[0] = 1;
        for(int i =2;i<=n;i++){
            for(int j =0;j<i;j++){
                dp[i] += dp[j]*dp[i-j-1];
            }
        }
        return dp[n];
    }
};

01背包

1. 分割等和子集：是否可以装满一个背包，物品的质量和价值相等，递推公式为dp[j] = max(dp[j], dp[j-nums[i]]+nums[i]);
2. 最后一块石头的重量II：对于一个背包来说，最大可以装多重的重量，物品的价值和质量依然相等,递推公式为dp[j]=max(dp[j],dp[j-stones[i]]+stones[i]);
   3.目标和：装满一个背包，一共有多少种装物品的方式，物品的价值和质量相等，递推公式为dp[j]+=dp[j-nums[i]];
   4.一和零：装满一个背包，最多可以装多少个物品，物品的价值为1，递推公式为dp[i][j] = max(dp[i][j],dp[i-zeronum][j-onenum]+1),此问题只是质量的维度为2，而不是多重背包。

分割等和子集

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum=0;
        for(int i =0;i<nums.size();i++){
            sum+=nums[i];
        }
        if(sum%2==1) return false;
        int bageweight = sum/2;
        vector<int> dp(bageweight+1,0);
        for(int i =0;i<nums.size();i++){
            for(int j = bageweight;j>=nums[i];j--){
               dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        if(dp[bageweight]==bageweight) return true;
        return false;
    }
};

1049.最后一块石头的重量II

这道题用动规的思路很难想。首先将这道题的题意分析后变成尽量让石头分成重量相同的两堆，然后动规的target就是其中一堆，类比上一题分割等和子集。我的dp[target]代表在重量为target的背包里最多能装多重的石头。而且最终分成的两堆，一堆dp[target],一堆sum-dp[target]一定可以通过若干个回合抵消到只有sum-dp[bagweight]-dp[bagweight]。

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum=0;
        for(int i =0;i<stones.size();i++) sum+=stones[i];
        int  bagweight= sum/2;
        vector<int> dp(bagweight+1,0);
        for(int i =0;i<stones.size();i++){
            for(int j =bagweight;j>=stones[i];j--){
                dp[j] = max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        return sum-dp[bagweight]-dp[bagweight];
    }
};

494.目标和

只能说目标和这道题，我在做的时候还是用dp[j]=max(dp[j],dp[j-nums[i]]+nums[i])去了，然后用一个数ans统计次数，dp数组的意义没设对，应该直接设dp[j]：代表凑出j有几种方法。然后递推公式是dp[j] += dp[j-nums[i]] ,也就是说

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum=0;
        for(int i =0;i<nums.size();i++){
            if(nums[i]<0){
                nums[i]=-nums[i];
            }
            sum+=nums[i];
        }
        if(target>sum||target<-sum||(target+sum)%2!=0) return 0;
        int bagweight = (sum+target)/2;
        vector<int> dp(bagweight+1,0);
        dp[0]=1;
        for(int i =0;i<nums.size();i++){
            for(int j=bagweight;j>=nums[i];j--){
                dp[j] +=dp[j-nums[i]];
            }
        }
        return dp[bagweight];
    }
};

474.一和零

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int> > dp(m+1,vector<int>(n+1,0));
        for(string str:strs)
        {
            int zeronum=0,onenum=0;
            for(char 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);
                    }
                }
        }
        return dp[m][n];
    }
};

完全背包

• 如果求组合数就是外层for循环遍历物品，内层for循环遍历背包
• 如果求排列数就是外层for循环遍历背包，内层for循环遍历物品
• 如果将爬楼梯改为一次1-m阶，那么这个问题就是一个完全背包问题了，而且求的是排列数，先遍历背包
• 求装满背包需要的最少物品数，一是注意dp数组的初始化vector dp(bagweight,INT_MAX)。二是注意dp[0]=0这个条件的初始化，三是注意dp的递推公式dp[j] =min(dp[j],dp[j-nums[i]]+1);

每件物品有无限个，其他条件一样。
01背包和完全背包体现在遍历顺序上，我们知道01背包内嵌的循环是从大到小遍历，为了保证每个物品仅仅被添加一次。但是完全背包的物品可以被多次添加，所以，要从小到大遍历。

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]);
	}
}

518.零钱兑换II

本质上是装满一个背包，一共有多少种装物品的方式，把目标和那道题改成完全背包的遍历方式即可。注意!!!初始化dp[0]=1

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1,0);
        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];
    }
};

组合总和IV

这道题求装满物品方式的个数的排列，排列和组合的区别是遍历方式，排列先便利背包，组合先遍历物品。

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target+1,0);
        dp[0]=1;
        for(int j =0;j<=target;j++){
            for(int i =0;i<nums.size();i++){
                if(j>=nums[i]&& dp[j] < INT_MAX - dp[j - nums[i]])dp[j] += dp[j-nums[i]];
            }
        }
        return dp[target];
    }
};

70.爬楼梯(进阶版)

题目改为一步一个台阶，两个台阶，三个台阶，…，直到m个台阶，问有多少种不同的方法可以爬到楼顶呢？
可以看成总的楼顶是背包，m阶是物品，这是一个完全背包问题，因为物品的数量为无限，且这是一个排列问题，因为(1,2,1)和(1,1,2)是两种走法。

求装满背包有几种方法，递推公式一般都是dp[j]+=dp[j-nums[i]]，本题目中进一步改写为dp[j]+=dp[j-i]；

class Solution {
public:
    int climbStairs(int n) {
       vector<int> dp(n+1，0);
       dp[0] = 1;
       int bagweighht;
       for(int j=1;i<=bagweight;i++){
       		for(int i =1;i<=m;i++){
       			dp[j]+=dp[j-i];
       		}
       }
       return dp[bagweight];
    }
};

零钱兑换

完全背包，求装满背包的最少可以装多少物品，迭代公式要用min。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,10010);
        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);
            }
        }
        if(dp[amount]==10010) return -1;
        else return dp[amount];
    }
};

279. 完全平方数

class Solution {
public:
    int numSquares(int n) {
       vector<int> dp(n+1,INT_MAX);
       dp[0] = 0;
       for(int i =1;i*i<=n;i++){
           for(int j =i*i;j<=n;j++){
               dp[j] = min(dp[j],dp[j-i*i]+1);
           }
       }
       return dp[n]; 
    }
};

139. 单词拆分

难理解的动规法，自己做加分析两种方法花了1h。

回溯法

//回溯法
class Solution {
public:
    bool backtracking(string s, unordered_set<string>& wordset,vector<bool>& memory,int startindex){
        if(startindex>=s.size()){
            return true;   //一般不会到这步，到这步说明str中的拆分字符串都在wordDict中找到了，自然要返回true
        }
        if(!memory[startindex]) return false;   //使用memory剪枝。
        for(int i =startindex;i<s.size();i++){
            string str = s.substr(startindex,i-startindex+1);
            if(wordset.count(str)!=0&& backtracking(s,wordset,memory,i+1)){ //如果该字符串str可被拆，并且str后面的字符串也可以被拆，则返回true
                return true;
            }
        }
        memory[startindex] = false;
        return false;
    }
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordset(wordDict.begin(), wordDict.end());
        //回溯+记忆化递归，相当于剪枝
        vector<bool> memory(s.size(),true);  //从startindex开始的字符串是否可被拆分，如果不可设为false，初始化全部为true
        return backtracking(s,wordset,memory,0);
    }
};

动规法

//回溯法
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        //dp[i]数组的含义：字符串长度为i时，是否可以被拆分成wordDict中的子串
        //物品是字符串，背包大小就是s的大小
        //递推公式：if(dp[i-j]&&wordset.count(str)!=0) dp[i]=false;
        vector<bool> dp(s.size()+1,false);
        dp[0] =true;
        unordered_set<string> wordset(wordDict.begin(),wordDict.end());
        //求排列，因为字符串是有顺序的，所有要遍历所有排列数
        for(int j = 1;j<=s.size();j++){
            for(int i =0;i<=j;i++){
                string str = s.substr(i,j-i); //j是长度，所以不用减一
                if(wordset.count(str)!=0&&dp[i]) dp[j]=true; 
                if(dp[j]==true) break;
            }
        }
        return dp[s.size()]; 
    }
};

多重背包

多重背包化为0-1背包

法一

直接将数量进行拆解

void test_multi_pack() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    vector<int> nums = {2, 3, 2};
    int bagWeight = 10;
    for (int i = 0; i < nums.size(); i++) {
        while (nums[i] > 1) { // nums[i]保留到1，把其他物品都展开
            weight.push_back(weight[i]);
            value.push_back(value[i]);
            nums[i]--;
        }
    }

    vector<int> dp(bagWeight + 1, 0);
    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]);
        }
        for (int j = 0; j <= bagWeight; j++) {
            cout << dp[j] << " ";
        }
        cout << endl;
    }
    cout << dp[bagWeight] << endl;

}
int main() {
    test_multi_pack();
}

背包问题总结

打家劫舍

198.打家劫舍

class Solution {
public:
    int rob(vector<int>& nums) {
      //dp数组的含义:当到达第下标为第i家的时候最多可以偷窃的金钱数
      vector<int> dp(nums.size(),0);
      if(nums.size()==1) return nums[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-1],dp[i-2]+nums[i]);
      }
      return dp[nums.size()-1];
    }
};

213.打家劫舍II

//成环需要考虑两种情况，不偷首，不偷尾
class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size()==1) return nums[0];
        int res1 = result(nums,1,nums.size()-1); //不偷首
        int res2 = result(nums,0,nums.size()-2); //不偷尾
        return max(res1,res2);
        
    }
    int result(vector<int>& nums,int start,int end)
    {
       vector<int> dp(end-start+1,0);
       if(dp.size()==1) return nums[start];
       dp[0] = nums[start];
       dp[1] = max(nums[start+1],nums[start]);
       for(int i =2;i<dp.size();i++){
           dp[i] = max(dp[i-1],dp[i-2]+nums[start+i]);
       }
       return dp[dp.size()-1];
    }
};

打家劫舍III

动规

class Solution {
public:
    int rob(TreeNode* root) {
        vector<int> res=robTree(root);
        return max(res[0],res[1]);
    }
    vector<int> robTree(TreeNode* cur)
    {
       if(cur==nullptr) return vector<int> {0,0};
       vector<int> left = robTree(cur->left);
       vector<int> right = robTree(cur->right);

       int val1 = cur->val+left[0]+right[0];
       int val2 = max(left[0],left[1])+max(right[0],right[1]);
       return {val2,val1};
    }
};

回溯

这道题回溯＋剪枝竟然比动规快，主要还是在于记忆化数组memory的运用。

class Solution {
public:
    unordered_map<TreeNode*,int> memory;
    int rob(TreeNode* cur) {
        if(cur==nullptr) return 0;
        if(cur->left==nullptr&&cur->right==nullptr) return cur->val;
        if(memory[cur]) return memory[cur];
        // 偷该节点
        int val1 = cur->val;
        int val2 = 0;
        if(cur->left) 
        {
            val1+=rob(cur->left->left)+rob(cur->left->right);
            val2+=rob(cur->left);
        }
        if(cur->right) {
            val1+=rob(cur->right->left)+rob(cur->right->right);
            val2+=rob(cur->right);
        }
        memory[cur] = max(val1,val2);
        return max(val1,val2);
    }
};

买卖股票的最佳时机

代码随想录总结

1. 买卖股票的最佳时机:只可以买卖一次，递推公式为：
   dp[i][0] = max(dp[i-1][0],-prices[i]);
   dp[i][1] = max(dp[i-1][1],prices[i]+dp[i-1][0]);

2. 买卖股票的最佳时机II:可以买卖多次，递推公式为：
   dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]); // 注意这里是和121. 买卖股票的最佳时机唯一不同的地方。
   dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);

3. 买卖股票的最佳时机III:只可以买卖两次，递推公式为：
   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]);

4. 买卖股票的最佳时机IV:可以买卖k次，递推公式为：
   for(int j =1;j<=2*k;j+=2){
   dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]-prices[i]);
   dp[i][j+1] = max(dp[i-1][j+1],dp[i-1][j]+prices[i]);
   }

5. 买卖股票的最佳时机含冷冻期：
   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];

6. 买卖故交的最佳时机含手续费：无限次交易：
   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);

121.买卖股票的最佳时机

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //dp[i][0]:第i天持有股票获得的最大现金
        //dp[i][1]:第i天不再持有股票获得的最大现金
        vector<vector<int> > dp(prices.size(),vector<int>(2,0));
        dp[0][0] = -prices[0];
        dp[0][1] = 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],prices[i]+dp[i-1][0]);
        }
        return dp[prices.size()-1][1];
    }
};

122买卖股票的最佳时机II

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<int> dp(prices.size(),0);
        for(int i =1;i<prices.size();i++){
                dp[i] = dp[i-1]+max(prices[i]-prices[i-1],0);
        }
        return dp[prices.size()-1];
    }
};

123.买卖股票的最佳时机III

class Solution {
public:
    int maxProfit(vector<int>& prices) {
    //dp[i][0]:没有操作
    //dp[i][1]:第一次买入股票拥有的最大现金数
    //dp[i][2]:第一次卖出股票拥有的最大现金数
    //dp[i][3]:第二次买入股票拥有的最大现金数
    //dp[i][4]:第二次卖出股票拥有的最大现金数
        vector<vector<int> > dp(prices.size(),vector<int>(5,0));
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        dp[0][2] = 0;
        dp[0][3] = -prices[0];
        dp[0][4] = 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];
    }
};

188.买卖股票的最佳时机IV

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        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];
            dp[0][j+1] = 0;
        }
        for(int i =1;i<prices.size();i++){
            for(int j =1;j<=2*k;j+=2){
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]-prices[i]);
                dp[i][j+1] = max(dp[i-1][j+1],dp[i-1][j]+prices[i]);
            }
        }
        return dp[prices.size()-1][2*k];
    }
};

309.最佳买卖股票时机含冷冻期

class Solution {
public:
    int maxProfit(vector<int>& prices) {
    // 状态一:持有股票状态(今天买入股票，或者之前就买入了股票然后没有操作，一直持有)的金钱数
    // 状态二:保持卖出股票的状态(两天前卖出了股票，度过一天冷冻期，或者前一天就是卖出股票状态)的金钱数
    // 状态三:今天卖出股票的金钱数
    // 状态四:今天是冷冻期状态，但冷冻期只有一天的金钱数
        if(prices.size()==0) return 0;
        vector<vector<int> > dp(prices.size(),vector<int>(4,0));
        dp[0][0] = -prices[0];
        for(int i =1;i<prices.size();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][3],dp[i-1][1]);
            dp[i][2] = dp[i-1][0]+prices[i];
            dp[i][3] = dp[i-1][2];
        }
        return max(dp[prices.size() - 1][3], max(dp[prices.size() - 1][1], dp[prices.size() - 1][2]));
    }
};

714.买卖股票的最佳时机含手续费

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]);
    }
};

子序列问腿

300.最长递增子序列

dp[i]:表示i之前包括i的以nums[i]结尾的最长递增子序列的长度
状态转移方程：
位置i的最长升序子序列等于j从0到i-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);
            }
            result = dp[i]>result?dp[i]:result;
        }
        return result;
    }
};

674.最长连续递增序列

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        if(nums.size()<=1) return nums[0];
        vector<int> dp(nums.size(),1);
        int res;
        for(int i =1;i<nums.size();i++)
        {
            if(nums[i]>nums[i-1]) dp[i] = dp[i-1]+1;
            res = dp[i]>res?dp[i]:res;
        }
        return res;
    }
};

718.最长重复子数组

• dp[i][j]：以下标i-1为结尾的A和以下标j-1为结尾的B，最长重复子数组长度为dp[i][j]，

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 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;
                }
                if(dp[i][j]>res) res = dp[i][j];
            }
        }
        return res;
    }
};

1143.最长公共子序列

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int> > dp(text1.size()+1,vector<int>(text2.size()+1,0));
        int res =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]);
                res = dp[i][j]>res?dp[i][j]:res;
            }
        }
        return res;
    }
};

1035.不相交的线

这道题本质上还在求最长公共子序列，记住最长公共子序列的迭代公式就可以a掉这道题。

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int> > dp(nums1.size()+1,vector<int>(nums2.size()+1,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;
                else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[nums1.size()][nums2.size()];
    }
};

53.最大子序和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size(),0);
        dp[0] = nums[0];
        int res = dp[0];
        for(int i =1;i<nums.size();i++)
        {
            dp[i] = max(dp[i-1]+nums[i],nums[i]);
            res = dp[i]>res?dp[i]:res;
        }
        return res;
    }
};

392.判断子序列

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;
        else return false;
    } 
};

不同的子序列

这道题用dp做很难想到

//dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]
class Solution {
public:
    int numDistinct(string s, string t) {
        vector<vector<uint64_t> > dp(s.size()+1,vector<uint64_t>(t.size()+1));
        //以下标0~i-1结尾的s串中，出现0字符串的个数
        //只有dp[0][0] = 1,其他都是复制的dp[0][0]
        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数组的含义，我主要想了很久的如果s[i - 1] == t[j - 1]，那么dp数组如何更新。如果使用s[i-1]去匹配，那么以i-1为结尾的s子序列中出现以j-1为结尾的t的个数就是以i-2为结尾的s子序列中出现以j-2为结尾的t的个数，即dp[i-1][j-1]。如果不使用s[i-1]去匹配，那么dp[i][j] = dp[i-1][j] ,所以此时dp[i][j]是两种情况的和。dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]

举个例子
s = “rabbbit”, t = “rabbit”
当s遍历到第2个b时，可以使用第二b去配，此时就是ra[]b，不使用第二b去配时，此时就是rab[]

583.两个字符串的删除操作

class Solution {
public:
    //dp[i][j]:以i-1为结尾的字符串word1和以j-1为结尾的字符串word2，想要达到相等，所需要删除元素的最少次数
    int minDistance(string word1, string word2) {
        vector<vector<int> > dp(word1.size()+1,vector<int>(word2.size()+1,0));
        //以i-1为结尾的字符串word1和空字符串的word2,想要达到相等，所需要删除元素的最少次数
        //以j-1为结尾的字符串word2和空字符串的word1,想要达到相等，所需要删除元素的最少次数
        //注意:j=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++){
                //如果word1[i-1]==word2[j-1] 不删
                if(word1[i-1]==word2[j-1]) dp[i][j] = dp[i-1][j-1];
                //否则删除其中一个
                else dp[i][j] = min(dp[i][j-1]+1,dp[i-1][j]+1);
            }
        }
        return dp[word1.size()][word2.size()];
    }
};

72.编辑距离

class Solution {
public:
    //本题和583两个字符的删除操作非常类似
    //dp[i][j]的含义为以下标i-1为结尾的字符串word1和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]
    //删除和添加需要的操作数次数是一样的：
    //word1:ad word2:a ,删除word1的d和增加word2的d都需要一次。所以延续583题的递推公式
    //word1 word2替换操作，此时dp[i][j] = dp[i-1][j-1]+1
    //因为dp[i][j] = dp[i-1][j-1]word1[i-1]和 word2[j-1]相等时的递推公式，只需再增加1，就变成了word1[i-1]==word2[j-1]这种情况
    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(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
            }
        }
        return dp[word1.size()][word2.size()];
    }
};

编辑距离总结

关于编辑距离的问题，我们从判断子序列开始一共做了4个题目。

判断子序列：给定字符串s和t是否为t的子序列实际上编辑距离不用考虑替换和添加操作的一道题目。

dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][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];

相同，则长度+1，不同则长度沿袭dp[i][j-1]

不同的子序列：给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。

if (s[i - 1] == t[j - 1]) {
   dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
   //一部分是用s[i - 1]来匹配，那么个数为dp[i - 1][j - 1]。
   //即不需要考虑当前s子串和t子串的最后一位字母，所以只需要 dp[i-1][j-1]。
   //一部分是不用s[i - 1]来匹配，个数为dp[i - 1][j]。
} else {
    dp[i][j] = dp[i - 1][j];
    //当s[i - 1] 与 t[j - 1]不相等时，dp[i][j]只有一部分组成，不用s[i - 1]来匹配（就是模拟在s中删除这个元素），即：dp[i - 1][j]
}

两个字符串的删除操作：给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

dp[i][j]：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。
当word1[i - 1] 与 word2[j - 1]相同的时候，dp[i][j] = dp[i - 1][j - 1];

当word1[i - 1] 与 word2[j - 1]不相同的时候，有三种情况：

情况一：删word1[i - 1]，最少操作次数为dp[i - 1][j] + 1

情况二：删word2[j - 1]，最少操作次数为dp[i][j - 1] + 1

情况三：同时删word1[i - 1]和word2[j - 1]，操作的最少次数为dp[i - 1][j - 1] + 2

那最后当然是取最小值，所以当word1[i - 1] 与 word2[j - 1]不相同的时候，递推公式：dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});

因为 dp[i][j - 1] + 1 = dp[i - 1][j - 1] + 2，所以递推公式可简化为：dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);

编辑距离：给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符

dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。

 //本题和583两个字符的删除操作非常类似
    //dp[i][j]的含义为以下标i-1为结尾的字符串word1和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]
    //删除和添加需要的操作数次数是一样的：
    //word1:ad word2:a ,删除word1的d和增加word2的d都需要一次。所以延续583题的递推公式
    //word1 word2替换操作，此时dp[i][j] = dp[i-1][j-1]+1
    //因为dp[i][j] = dp[i-1][j-1]word1[i-1]和 word2[j-1]相等时的递推公式，只需再增加1，就变成了word1[i-1]==word2[j-1]这种情况
 if(word1[i-1]==word2[j-1]) dp[i][j] = dp[i-1][j-1];
 else dp[i][j] = min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;

647.回文子串

动态规划法

1. 确定dp数组以及下标的含义：
   布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。
2. 确定递推公式：
   当s[i]与s[j]不相等，dp[i][j]一定是false。
   当s[i]与s[j]相等时，如果j-i<=1,则依然是回文子串。如果j-i>1,则是否是回文子串依赖于dp[i+1][j-1]
   

class Solution {
public:
    int countSubstrings(string s) {
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
        int res= 0;
        for(int i =s.size()-1;i>=0;i--){
            for(int j =i;j<s.size();j++){
                if(s[i]!=s[j]) dp[i][j]=false;
                else{
                    if(j-i<=1){
                        dp[i][j] = true;
                        res++;
                    } 
                    else if(dp[i+1][j-1]){
                        dp[i][j] = true;
                        res++;
                    } 
                }
            }
        }
        return res;
    }
};

双指针法

class Solution {
public:
    int countSubstrings(string s) {
        int res=0;
        for(int i =0;i<s.size();i++){
            res+=extend(s,i,i,s.size());
            res+=extend(s,i,i+1,s.size());
        }
        return res;
    }
    int extend(string& s,int i, int j, int n){
        int res = 0;
        while(i>=0&&j<n&&s[i]==s[j]){
            i--;
            j++;
            res++;
        }
        return res;
    }
};

516.最长回文子序列

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()-2;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];
    }
};