leetcode-常规 - 2. 动态规划 - 《算法刷题》

1. 62. 不同路径

class Solution {
public:
    int uniquePaths(int m, int n) {
        //定义数组，表示为 从左上角走到(i，j)共有dp[i][j]个路径
        vector<vector<int>> dp(m,vector<int>(n));
        //找初始值
        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];
    }
};

2. 64. 最小路径和

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        //定义数组: 表示 从左上角到（i，j）路径上的数字总和
        vector<vector<int>> dp(grid.size(),vector<int>(grid[0].size()));
        //找初始值
        dp[0][0]=grid[0][0];
        for(int i=1;i<grid.size();i++){
            dp[i][0]=grid[i][0]+dp[i-1][0];
        }
        for(int j=1;j<grid[0].size();j++){
            dp[0][j]=grid[0][j]+dp[0][j-1];
        }
        //找关系
        for(int i=1;i<grid.size();i++){
            for(int j=1;j<grid[0].size();j++){
                dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[grid.size()-1][grid[0].size()-1];
    }
};

3. 72. 编辑距离

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m=word1.size()+1;
        int n=word2.size()+1;
        //定义数组，dp[i][j]表示 word1长度为 i，word2 长度为 j ，从 word1 转换为word2所需要的最小操作数。
        vector<vector<int>> dp(m,vector<int>(n,0));
        for(int i=0;i<m;i++){
            dp[i][0]=i;
        }
        for(int j=0;j<n;j++){
            dp[0][j]=j;
        }
        //找关系
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                // 字符相同时，对应下表为i-1和j-1
                if(word1[i-1]==word2[j-1]){
                    dp[i][j]=dp[i-1][j-1];
                }else{
                    //插入时  dp[i][j]=d[i][j-1]+1;
                    //删除时，dp[i][j]=d[i-1][j]+1;  
                    //替换时，dp[i][j]=d[i-1][j-1]+1;
                    dp[i][j]=min(dp[i][j-1],min(dp[i-1][j],dp[i-1][j-1]))+1;
                }
            }
        }
        return dp[m-1][n-1];        
    }
};

4. 198. 打家劫舍

class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        //定义数组,小偷到达i号屋子时最高可偷盗的金额为dp[i].
        vector<int> dp(n,0);
        if(n<2){
            return nums[0];
        }
        //初始值
        dp[0]=nums[0];
        dp[1]=max(nums[0],nums[1]);
        //找关系式
        for(int i=2;i<n;i++){
            dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[n-1];
    }
};
//优化，仅用2个变量保存之前的状态
class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        if(n<2){
            return nums[0];
        }
        int dp_0=nums[0];
        int dp_1=max(dp_0,nums[1]);    
        //transform 
        for(int i=2;i<n;i++){
            int temp=max(dp_0+nums[i],dp_1);
            dp_0=dp_1;
            dp_1=temp;
        }
        return dp_1;
    }
};
//另外一种方法
class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        //base case
        if(n==1){
            return nums[0];
        }
        if(n==2){
            return max(nums[0],nums[1]);
        }
        return helper(nums,0,n-1);
    }
    int helper(vector<int>& nums,int start,int end){
        int n=end-start+1;
        //status and define and base case
        int dp_0=nums[start];
        int dp_1=max(nums[start],nums[start+1]);
        //transform
        for(int i=2;i<n;i++){
            int temp=max(dp_0+nums[start+i],dp_1);
            dp_0=dp_1;
            dp_1=temp;
        }
        return dp_1;
    }
};

5. 53. 最大子数组和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n=nums.size();
        //define  dp[i]是以num[i]结尾的最大序列和
        vector<int> dp(n,0);

        //edge
        if(n==0){
            return 0;
        }
        dp[0]=nums[0];

        //relation，填充dp，并从中找出最大值
        int m_max=dp[0];
        for(int i=1;i<n;i++){
            dp[i]=max(dp[i-1]+nums[i],nums[i]);
            if(dp[i]>m_max){
                m_max=dp[i];
            }
        }
        return m_max;
    }
};

//优化
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n=nums.size();

        //edge
        if(n==0){
            return 0;
        }

        //define 
        int dp=nums[0];

        //relation，填充dp，并从中找出最大值
        int m_max=dp;
        for(int i=1;i<n;i++){
            dp=max(dp+nums[i],nums[i]);
            if(dp>m_max){
                m_max=dp;
            }
        }
        return m_max;
    }
};

6. 322. 零钱兑换

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {

        //define dp[i]表示 凑成金额为i所需要的最少的硬币个数      

        //为了防止后边min操作覆盖 dp[i],要给dp赋初值，并且初值要尽量大。
        vector<int> dp(amount+1,amount+1);

        //edge
        dp[0]=0;

        //relation
        for(int i=1;i<dp.size();i++){
            for(int j=0;j<coins.size();j++){
                if(coins[j]<=i){
                    dp[i]=min(dp[i-coins[j]]+1,dp[i]);    
                }
            }
        }

        return dp[amount]>amount?-1:dp[amount];

    }
};

7. 300. 最长递增子序列

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        //define dp[i]表示以nums[i]结尾的最长递增子序列长度
        int n=nums.size();

        //edge
        vector<int> dp(n,1);    //自身也属于子序列的一部分，初始化为1

        //relation
        int m_max=dp[0];
        for(int i=1;i<n;i++){    //判断nums[i]是否加入到计数中   
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i]){   //找出i之前的最长递增子序列 用j
                    dp[i]=max(dp[i],dp[j]+1);   
                }
            }  
            m_max=max(m_max,dp[i]);                       
        }     
        return m_max;
    }
};

8. 931. 下降路径最小和

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        //define dp[i][j]表示从开始元素到（i,j）的下降路径最小和
        int n=matrix.size();
        vector<vector<int>> dp(n,vector<int>(n,0));

        //edge
        if(n<=0){
            return 0;
        }
        dp[0][0]=matrix[0][0];

        //relation.要考虑边界，分情况讨论
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(i==0){
                    dp[i][j]=matrix[0][j];
                }else if(j==0){
                    dp[i][j]=min(dp[i-1][0],dp[i-1][1])+matrix[i][j];
                }else if(j==n-1){
                    dp[i][j]=min(dp[i-1][j],dp[i-1][j-1])+matrix[i][j];
                }else{
                    dp[i][j]=min(dp[i-1][j],min(dp[i-1][j+1],dp[i-1][j-1]))+matrix[i][j];
                }
            }
        }
        //最后一行还没计算，终点在最后一行时
        int m_min=INT_MAX;
        for(int j=0;j<n;j++){
            m_min=min(dp[n-1][j],m_min);
        }
        return m_min;
    }
};


//套壳，不必考虑边界
class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n=matrix.size();
        //后边涉及到 j-1 j+1 j, 套壳处理
        //status and define
        vector<vector<int>> dp(n+1,vector<int>(n+2,0));

        //base case 
        for(int i=0;i<=n;i++){
            dp[i][0]=INT_MAX;
            dp[i][n+1]=INT_MAX;
        }   

        // transform        
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(dp[i][j]==100001){
                    return dp[i][j];
                }
                dp[i][j]=min(dp[i-1][j+1],min(dp[i-1][j],dp[i-1][j-1]))+matrix[i-1][j-1];
            }
        }

        //最后一行 取最小
        int res=INT_MAX;
        for(int j=0;j<=n;j++){
            res=min(res,dp[n][j]);
        }
        return res;
    }
};

9. 279. 完全平方数

class Solution {
public:
    int numSquares(int n) {
        //define  dp[i]表示 和为i ...最少数量。
        vector<int> dp(n+1,0);

        //edge
        if(n<0){
            return 0;
        }
        dp[0]=0;

        //relation: dp[i]=dp[i-j*j]+1
        int m_min;
        for(int i=1;i<=n;i++){
            m_min=INT_MAX;  //为了取到 dp[i]减去一个平方数后的最小数，说明减去的这个平方数最大
            //找到最大的平方数
            for(int j=1;j*j<=i;j++){
                m_min=min(m_min,dp[i-j*j]);
            }
            dp[i]=m_min+1;
        }
        return dp[n];
    }
};

10. 121. 买卖股票的最佳时机和剑指 Offer 63. 股票的最大利润

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //define dp[i]表示 第i天可获得的最高利润
        vector<int> dp(prices.size(),0);

        //edge 
        dp[0]=0;
        int m_min=prices[0];   //买入时机最低价格
        int m_max=0; //过去的天中利润最高值

        //relation
        for(int i=1;i<prices.size();i++){  
            if(m_min>prices[i]){
                m_min=prices[i];
            }          
            dp[i]=max(dp[i-1],prices[i]-m_min);  
            m_max=max(m_max,dp[i]);          
        }

        return m_max;
    }
};


//状态转移框架
class Solution {
public:
    int maxProfit(vector<int>& prices){
        int n=prices.size();

        //status and define 
        vector<vector<int>> dp(n,vector<int>(2));

        //base case
        dp[0][0]=0;  //没持有股票
        dp[0][1]=-prices[0];      //不可能持有股票

        //transform
        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],-prices[i]);
        }
        return dp[n-1][0];
    }
};


//动态规划进一步优化
class Solution {
public:
    int maxProfit(vector<int>& prices){
        //仅用两个变量来保存
        // status and base case
        int dp_i_0=0;   //没持有股票
        int dp_i_1=-prices[0];  //不可能持有股票

        // transform 
        for(int i=1;i<prices.size();i++){
            dp_i_0=max(dp_i_0,dp_i_1+prices[i]);
            dp_i_1=max(dp_i_1,-prices[i]);
        }

        return dp_i_0;
    }
};

11. 122. 买卖股票的最佳时机 II

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        //status and define
        //base case,只有1天是不能买入的，因为无法卖出
        if(n<2){
            return 0;
        }
        int dp_i_0=0;   
        int dp_i_1=-prices[0];

        //transform
        for(int i=1;i<n;i++){
            dp_i_0=max(dp_i_0,dp_i_1+prices[i]);
            dp_i_1=max(dp_i_1,dp_i_0-prices[i]);
        }

        return dp_i_0;   

    }
};

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

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        // status and define
        vector<vector<int>> dp(n,vector<int>(2));

        // base case
        if(n<2){
            return 0;
        }
        dp[0][0]=0;
        dp[0][1]=-prices[0];
        dp[1][0]=max(dp[0][0],dp[0][1]+prices[1]);  //i-2=-1时
        dp[1][1]=max(dp[0][1],dp[0][0]-prices[1]);

        //transform
        for(int i=2;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-2][0]-prices[i]);
        }
        return dp[n-1][0];
    }
};


//优化
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();

        // base case
        if(n<2){
            return 0;
        }

        // status and define
        int dp_i_0=0;
        int dp_i_1=-prices[0];
        int dp_pre=0;   //n-2        

        //transform
        for(int i=0;i<n;i++){
            int temp=dp_i_0;
            dp_i_0=max(dp_i_0,dp_i_1+prices[i]);
            dp_i_1=max(dp_i_1,dp_pre-prices[i]);
            dp_pre=temp;
        }
        return dp_i_0;
    }
};

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

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n=prices.size();

        //status and define
        vector<vector<int>> dp(n,vector<int>(2));

        //base case
        if(n<2){
            return 0;
        }
        dp[0][0]=0;
        dp[0][1]=-prices[0]-fee;

        //transform
        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 dp[n-1][0];       
    }
};

//优化
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n=prices.size();

        //base case
        if(n<2){
            return 0;
        }

        //status and define
        int dp_i_0=0;
        int dp_i_1=-prices[0]-fee;

        //transform
        for(int i=1;i<n;i++){
            dp_i_0=max(dp_i_0,dp_i_1+prices[i]);
            dp_i_1=max(dp_i_1,dp_i_0-prices[i]-fee);
        }
        return dp_i_0;       
    }
};

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

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        int k_max=2;

        //status and define 
        vector<vector<vector<int>>> dp(n,vector<vector<int>>(k_max+1,vector<int>(2)));

        //base case
        if(n<2){
            return 0;
        }

        for(int i=0;i<n;i++){
            for(int k=k_max;k>0;k--){
                //base case
                if(i==0){
                    dp[i][k][0]=0;
                    dp[i][k][1]=-prices[i];
                    continue;
                }
                //transform
                dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i]);
                dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i]);
            }
        }
        return dp[n-1][k_max][0];
    }
};

//优化
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        int k_max=2;

        //base case
        if(n<2){
            return 0;
        }

        //status and define 
        int dp_i20=0;
        int dp_i21=-prices[0];   //实际情况是不可能出现的
        int dp_i10=0;
        int dp_i11=-prices[0];

        for(int i=0;i<n;i++){
            dp_i20=max(dp_i20,dp_i21+prices[i]);
            dp_i21=max(dp_i21,dp_i10-prices[i]);
            dp_i10=max(dp_i10,dp_i11+prices[i]);
            dp_i11=max(dp_i11,-prices[i]);
        }
        return dp_i20;
    }
};

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

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n=prices.size();

        //status and define
        vector<vector<vector<int>>> dp(n,vector<vector<int>>(k+1,vector<int>(2)));

        if(n<2){
            return 0;
        }

        //k没有限制时，交易需要两次：买入和卖出
        if(k>n/2){
            int dp_i_0=0;
            int dp_i_1=-prices[0];
            for(int i=1;i<n;i++){
                dp_i_0=max(dp_i_0,dp_i_1+prices[i]);
                dp_i_1=max(dp_i_1,dp_i_0-prices[i]);
            }
            return dp_i_0;
        }

        //k有限制时
        //base case : k=0
        for(int i=0;i<n;i++){
            dp[i][0][0]=0;
            dp[i][0][1]=INT_MIN;
        }

        for(int i=0;i<n;i++){
            for(int j=k;j>0;j--){
                if(i-1==-1){
                    //i=-1时的base case 
                    dp[i][j][0]=0;
                    dp[i][j][1]=-prices[i];
                    continue;
                }
                dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]+prices[i]);
                dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i]);

            }
        }
        return dp[n-1][k][0];
    }
};

16. 650. 只有两个键的键盘

class Solution {
public:
    int minSteps(int n) {
        // status and define
        vector<vector<int>> dp(n+1,vector<int>(n+1,n+1));

        //base case
        if(n<1){
            return 0;
        }
        dp[1][0]=0;
        dp[1][1]=1;

        int m_min;
        for(int i=2;i<=n;i++){
            m_min=n+1;
            for(int j=1;j<=i;j++){
                if(i==j){   //choice 如果是剪切
                    dp[i][j]=m_min+1;
                }else{  // choice 如果是复制 
                    dp[i][j]=dp[i-j][j]+1;
                    m_min=min(m_min,dp[i][j]);
                }
            }
        }

        //找 dp[n][x]中最小的 x=1...n
        m_min=n+1;
        for(int i=0;i<=n;i++){
            m_min=min(dp[n][i],m_min);
        }
        return m_min;
    }
};

17. 1884. 鸡蛋掉落-两枚鸡蛋

class Solution {
public:
    int twoEggDrop(int n) {

        //status and define 
        vector<vector<int>> dp(2,vector<int>(n+1,n+1));

        //base case
        if(n<1){
            return 0;
        }
        dp[0][0]=0;
        dp[1][0]=0;
        for(int i=1;i<=n;i++){
            dp[0][i]=i;
        }

        // transform 
        for(int i=1;i<=n;i++){
            for(int j=1;j<=i;j++){
                dp[1][i]=min(dp[1][i],max(dp[0][j-1],dp[1][i-j])+1);
            }            
        }

        return dp[1][n];        
    }
};

18. 213. 打家劫舍 II

class Solution {
public:
    int rob(vector<int>& nums) {
        //base case  
        int n=nums.size();  
        if(n==1){
            return nums[0];
        }
        if(n==2){
            return max(nums[0],nums[1]);
        }   
        // 在0...n-2之中 或 1...n-1 之中  
        return max(helper(nums,0,n-2),helper(nums,1,n-1));
    }

    int helper(vector<int>& nums, int start, int end){   
        int m=end-start+1;          

        //status and define 
        vector<int> dp(m,0); 

        //base case 
        dp[0]=nums[start];
        dp[1]=max(nums[start],nums[start+1]);

        //transform
        for(int i=2;i<m;i++){
            dp[i]=max(dp[i-2]+nums[start+i],dp[i-1]);
        }
        return dp[m-1];
    }
};


//优化
class Solution {
public:
    int rob(vector<int>& nums) {
        //base case  
        int n=nums.size();  
        if(n==1){
            return nums[0];
        }
        if(n==2){
            return max(nums[0],nums[1]);
        }   
        // 在0...n-2之中 或 1...n-1 之中  
        return max(helper(nums,0,n-2),helper(nums,1,n-1));
    }

    int helper(vector<int>& nums, int start, int end){   
        int m=end-start+1;          

        //status and define 
        int dp_0=nums[start];
        int dp_1=max(nums[start],nums[start+1]);

        //transform
        for(int i=2;i<m;i++){
            int temp=max(dp_0+nums[start+i],dp_1);
            dp_0=dp_1;
            dp_1=temp;
        }
        return dp_1;
    }
};

19. 337. 打家劫舍 III

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> helper(TreeNode* root){
        vector<int> dp(2,0);
        if(!root){
            return dp;
        }
        vector<int> left=helper(root->left);
        vector<int> right=helper(root->right);
        dp[0]=max(left[0],left[1])+max(right[0],right[1]);
        dp[1]=left[0]+right[0]+root->val;
        return dp;

    }

    int rob(TreeNode* root) {
        vector<int> res=helper(root);
        return max(res[0],res[1]);
    }
};

20. 416. 分割等和子集

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n=nums.size();
        int sum=0;
        for(int i=0;i<n;i++){
            sum+=nums[i];
        }
        if(sum%2!=0){
            return false;
        }
        sum=sum/2;

        //status and define 
        vector<vector<bool>> dp(n+1,vector(sum+1,false));

        //base case    
        for(int i=0;i<n;i++){
            dp[i][0]=true;
        } 

        //transform 
        for(int i=1;i<=n;i++){
            for(int j=1;j<=sum;j++){
                if(j-nums[i-1]<0){
                    dp[i][j]=dp[i-1][j];
                }else{
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-nums[i-1]]);
                }
            }
        }

        return dp[n][sum];
    }
};

//优化，状态压缩，二维数组转化为一维
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n=nums.size();
        int sum=0;
        for(int i=0;i<n;i++){
            sum+=nums[i];
        }
        if(sum%2!=0){
            return false;
        }
        sum=sum/2;

        //status and define 
        vector<bool> dp(sum+1,false);

        //base case   
        dp[0]=true;



        for(int i=0;i<n;i++){
            //j应该从后往前反向遍历，因为每个物品（或者说数字）只能用一次，以免之前的结果影响其他的结果。
            for(int j=sum;j>=0;j--){
                if(j-nums[i]>=0){
                    dp[j]=max(dp[j],dp[j-nums[i]]);
                }
            }
        }

        return dp[sum];
    }
};

21. 518. 零钱兑换 II

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n=coins.size();

        //status and define
        vector<vector<int>> dp(n+1,vector<int>(amount+1));

        //base case
        for(int i=0;i<=n;i++){
            dp[i][0]=1;
        }

        //transform
        for(int i=1;i<=n;i++){
            for(int j=1;j<=amount;j++){
                if(j-coins[i-1]>=0){
                    dp[i][j]=dp[i][j-coins[i-1]]+dp[i-1][j];
                }else{
                    dp[i][j]=dp[i-1][j];
                }               
            }
        }
        return dp[n][amount];
    }
};

//优化，一维dp
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n=coins.size();

        //status and define
        vector<int> dp(amount+1);

        //base case
        dp[0]=1;

        //transform
        for(int i=1;i<=n;i++){
            for(int j=1;j<=amount;j++){
                if(j-coins[i-1]>=0){
                    dp[j]=dp[j-coins[i-1]]+dp[j];
                }             
            }
        }
        return dp[amount];
    }
};

22. 516. 最长回文子序列

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n=s.size();

        //status and define 
        vector<vector<int>> dp(n,vector<int>(n));

        //base case
        for(int i=0;i<n;i++){
            dp[i][i]=1;
        }

        //transform
        for(int i=n-1;i>=0;i--){
            for(int j=i+1;j<n;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][n-1];
    }
};

//优化，二维转一维dp
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n=s.size();

        //status and define 
        //base case
        vector<int> dp(n,1);

        //transform
        for(int i=n-1;i>=0;i--){
            //remember the last dp , dp[i+1]
            int pre=0;
            for(int j=i+1;j<n;j++){
                //remember the last dp , dp[i+1]
                int temp=dp[j];
                if(s[i]==s[j]){
                    // dp[i][j]=dp[i+1][j-1]+2;
                    dp[j]=pre+2;
                }else{
                    // dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
                    dp[j]=max(dp[j],dp[j-1]);
                }
                pre=temp;
            }
        }
        return dp[n-1];
    }
};

23. 1143. 最长公共子序列

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n1=text1.length();
        int n2=text2.length();

        //status and define 
        vector<vector<int>> dp(n1+1,vector<int>(n2+1));

        //base case 
        for(int i=0;i<=n1;i++){
            dp[i][0]=0;
        }
        for(int j=0;j<=n2;j++){
            dp[0][j]=0;
        }

        //transform
        for(int i=1;i<=n1;i++){
            for(int j=1;j<=n2;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[n1][n2];
    }
};

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

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n1=word1.length();
        int n2=word2.length();

        //status and define and base case
        vector<vector<int>> dp(n1+1,vector<int>(n2+1,0));

        //transform
        for(int i=1;i<=n1;i++){
            for(int j=1;j<=n2;j++){
                if(word1[i-1]==word2[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 n1-dp[n1][n2]+n2-dp[n1][n2];
    }
};

25. 712. 两个字符串的最小ASCII删除和

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int n1=s1.length();
        int n2=s2.length();

        //status and define  表示最长公共子序列的各个字符ascii码之和
        vector<vector<int>> dp(n1+1,vector<int>(n2+1,0));        

        //base case
        int sum=0; 
        for(int i=0;i<s1.length();i++){
            sum+=(int)s1[i];
        }
        for(int j=0;j<s2.length();j++){
            sum+=(int)s2[j];
        }

        //transform
        for(int i=1;i<=n1;i++){
            for(int j=1;j<=n2;j++){
                if(s1[i-1]==s2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+(int)s1[i-1];
                }else{
                    //取最大，删除的字符之和就最小了
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return sum-2*dp[n1][n2];
    }
};

26. 338. 比特位计数

class Solution {
public:
    vector<int> countBits(int n) {
        //status and define 
        vector<int> dp(n+1);

        //正整数 y 是 2 的整数次幂，则 y 的二进制表示中只有最高位是 1，其余都是 0，因此 y & (y−1)=0
        //transform
        int highbit=0;
        for(int i=1;i<=n;i++){
            if((i&(i-1))==0){
                highbit=i;
            }
            dp[i]=dp[i-highbit]+1;
        }
        return dp;
    }
};

27. 70. 爬楼梯

class Solution {
public:
    int climbStairs(int n) {
        // status and define 
        vector<int> dp(n+2);

        //base case
        dp[0]=1;
        dp[1]=1;

        //transform
        for(int i=2;i<n+1;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
};

//优化
class Solution {
public:
    int climbStairs(int n) {
        int dp_0=1;
        int dp_1=1;

        for(int i=2;i<n+1;i++){
            int temp=dp_0+dp_1;
            dp_0=dp_1;
            dp_1=temp;
        }
        return dp_1;
    }
};

2. 动态规划

1. 62. 不同路径

2. 64. 最小路径和

3. 72. 编辑距离

4. 198. 打家劫舍

5. 53. 最大子数组和

6. 322. 零钱兑换

7. 300. 最长递增子序列

8. 931. 下降路径最小和

9. 279. 完全平方数

10. 121. 买卖股票的最佳时机 和 剑指 Offer 63. 股票的最大利润

11. 122. 买卖股票的最佳时机 II

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

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

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

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

16. 650. 只有两个键的键盘

17. 1884. 鸡蛋掉落-两枚鸡蛋

18. 213. 打家劫舍 II

19. 337. 打家劫舍 III

20. 416. 分割等和子集

21. 518. 零钱兑换 II

22. 516. 最长回文子序列

23. 1143. 最长公共子序列

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

25. 712. 两个字符串的最小ASCII删除和

26. 338. 比特位计数

27. 70. 爬楼梯

10. 121. 买卖股票的最佳时机和剑指 Offer 63. 股票的最大利润