东哥经典动态规划

labuladong 的经典动态规划题

53.最大子数组和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n=nums.size();
        vector<int> dp(n);
        //base case
        dp[0]=nums[0];

        for(int i=1;i<n;i++){
            dp[i]=max(dp[i-1]+nums[i], nums[i]);
        }
        int res=INT_MIN;
        for(int i=0;i<n;i++){
            res = max(res, dp[i]);
        }
        return res;
    }
};

1800.最大升序子数组和

class Solution {
public:
    int maxAscendingSum(vector<int>& nums) {
        int n=nums.size();
        vector<int> dp(n);

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

        for(int i=1;i<n;i++){
            if(nums[i]>nums[i-1]){
                dp[i]=max(dp[i-1]+nums[i], nums[i]);
            }else{
                dp[i]=nums[i];
            }
        }
        int res=INT_MIN;
        for(int i=0;i<n;i++){
            res = max(res, dp[i]);
        }
        return res;
    }
};

1186.删除一次得到子数组最大和

class Solution {
public:
    int maximumSum(vector<int>& arr) {
        int n=arr.size();
        int res=INT_MIN;

        //dp0[i]代表以arr[i]为结尾的最大连续子数组和
        vector<int> dp0(n);  
        //dp1[i]代表以arr[i]为结尾的并且删除了一个元素（可能是arr[i]自己）后最大的连续子数组和
        vector<int> dp1(n); 

        //base case
        dp0[0]=arr[0];
        dp1[0]=arr[0]; //因为删除元素后不能为空，所以dp1[0]=arr[0];

        for(int i=1;i<n;i++){
            dp0[i]=max(dp0[i-1]+arr[i], arr[i]);
            dp1[i]=max(dp0[i-1], dp1[i-1]+arr[i]);
        }

        for(int i=0;i<n;i++){
            res = max(dp0[i], res);
            res = max(dp1[i], res);
        }
        return res;
    }
};

152.乘积最大子数组

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n=nums.size();

        //dp_min[i] 以 nums[i] 结尾的连续子数组的乘积的最小值
        //dp_max[i] 以 nums[i] 结尾的连续子数组的乘积的最大值

        vector<int> dp_min(n);
        vector<int> dp_max(n);
        
        //base case
        dp_max[0]=nums[0];
        dp_min[0]=nums[0];

        for(int i=1;i<n;i++){
            if(nums[i]>=0){
                dp_max[i]=max(dp_max[i-1]*nums[i], nums[i]);
                dp_min[i]=min(dp_min[i-1]*nums[i], nums[i]);
            }else{
                dp_max[i]=max(dp_min[i-1]*nums[i], nums[i]);
                dp_min[i]=min(dp_max[i-1]*nums[i], nums[i]);
            }
        }
        int res=INT_MIN;
        for(int i=0;i<n;i++){
            res = max(res, dp_max[i]);
        }
        return res;
    }
};

64.最小路径和

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        //动态规划
        int m=grid.size();
        int n=grid[0].size();
        vector<vector<int>> dp(m,vector<int>(n));

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

        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=min(dp[i-1][j], dp[i][j-1])+grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
};

72.编辑距离

class Solution {
public:
    int minDistance(string word1, string word2) {
        //word1[0..i] 和 word2[0..j] 的最小编辑距离是 dp[i][j]
        int m=word1.size();
        int n=word2.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1));

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

        for(int j=1;j<=n;j++){
            dp[0][j]=j;
        }

        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(word1[i-1]==word2[j-1]){
                    dp[i][j]=dp[i-1][j-1];    //什么都不做
                }else{
                    //dp[i-1][j] 删除，dp[i][j-1]插入，dp[i-1][j-1]替换
                    dp[i][j]=min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1])+1;
                }
            }
        }
        return dp[m][n];
    }
};

300.最长递增子序列

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

        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                //寻找nums[0...j-1]中比nums[i]小的元素
                if(nums[i]>nums[j]){
                    //把nums[i]接在后面，形成长度为dp[j]+1，且以nums[i]为结尾的递增子序列
                    dp[i]=max(dp[i], dp[j]+1);
                }
            }
        }
        int res=0;
        for(int i=0;i<n;i++){
            res = max(res, dp[i]);
        }
        return res;
    }
};

354.俄罗斯套娃信封问题

这道题目是最长递增子序列的一个变种，相当于在二维平面中找一个最长递增子序列，其长度就是最多能嵌套的信封个数。

思路：先对宽w进行升序排序，如果遇到w相等，则按照高度h降序排序；之后把所有的h作为一个数组，在这个数组上计算最长递增子序列的长度就是答案。

class Solution {
public:
    static bool Cmp(vector<int>& a, vector<int>& b){
        if(a[0]==b[0]){
            return a[1]>b[1];
        }
        return a[0]<b[0];
    }
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        //按照 w 升序排列，如果 w 相等，则按照 h 降序排列
        sort(envelopes.begin(), envelopes.end(), Cmp);
        int n=envelopes.size();
        vector<int> nums(n);
        for(int i=0;i<n;i++){
            nums[i]=envelopes[i][1];
        }
        int res = LIS(nums);
        return res;
    }
    //最长递增子序列
    int LIS(vector<int>& nums){
        int n=nums.size();
        vector<int> dp(n, 1);

        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    dp[i]=max(dp[i], dp[j]+1);
                }
            }
        }
        int res=0;
        for(int i=0;i<n;i++){
            res=max(res, dp[i]);
        }
        return res;
    }
};

673.最长递增子序列的个数

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n=nums.size();
        vector<int> dp(n, 1); //以nums[i]结尾的最长上升子序列的长度
        vector<int> count(n, 1); //以nums[i]结尾的最长上升子序列的个数

        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    if(dp[j]+1 > dp[i]){
                        count[i] = count[j];
                    }else if(dp[j]+1 == dp[i]){
                        count[i] +=count[j];
                    }
                    dp[i]=max(dp[i], dp[j]+1);
                }
            }
        }

        int res = 0;
        for(int i=0;i<n;i++){
            res=max(res, dp[i]);
        }

        int result = 0;
        for(int i=0;i<n;i++){
            if(dp[i]==res) result += count[i];
        }
        
        return result;
    }
};

1143.最长公共子序列

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m=text1.size();
        int n=text2.size();
        //定义：对于text1[0...i-1] 和 text2[0...j-1]，的最长公共子序列为 dp[i][j]
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));

        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(text1[i-1]==text2[j-1]){
                    //找到一个lcs中的元素
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    //至少有一个字符不在 lcs 中
                    dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[m][n];
    }
};

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

class Solution {
public:
    int minDistance(string word1, string word2) {
        //删除之后的结果，就是最长公共子序列;
        int m=word1.size();
        int n=word2.size();
        
        return m+n-2*LCS(word1, word2);
    }
    int LCS(string s1, string s2){
        int m=s1.size();
        int n=s2.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));

        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(s1[i-1]==s2[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[m][n];
    }
};

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

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int m=s1.size(); 
        int n=s2.size();
        //dp[i][j]代表s1[:i]和s2[:j]的最小删除和
        vector<vector<int>> dp(m+1,vector<int>(n+1, 0));

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

        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(s1[i-1]==s2[j-1]){
                    dp[i][j]=dp[i-1][j-1];
                }else{
                    dp[i][j]=min(dp[i-1][j]+s1[i-1], dp[i][j-1]+s2[j-1]);
                }
            }
        }
        return dp[m][n];
    }
};

718.最长重复子数组

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        //动态规划：dp[i][j]表示 nums1[0...i-1]和nums2[0...j-1]结尾的最长重复子数组
        int m=nums1.size();
        int n=nums2.size();
        int res = INT_MIN;
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));

        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(nums1[i-1]==nums2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                res = max(res, dp[i][j]);
            }
        }
        return res;
    }
};