动态规划高频题

会与面经题有一个重复的，比如最大股票收益，因为是动归系列，放在一起总结。

1.最大子数和：

求子序列的最大和 ，用到一维数组动归，状态转移方程是

dp[i]=max(dp[i-1]+nums[i],nums[i]);

如果nums[i]比dp[i-1]+nums[i]大的话，就以前者为一个新的起点，因为子数组是要连续的，所以新起点就要是num[i]

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int max1=nums[0];
        int dp[100001];
        dp[0]=nums[0];

        for(int i=1;i<nums.size();i++){
            dp[i]=max(dp[i-1]+nums[i],nums[i]);
            max1=max(max1,dp[i]);
        }
        
        return max1;
    }
};

2.买卖股票最佳时机-不会

还有一个类似的买卖股票最大实际，样例一样但输出不一样，一个是7一个5

这里就是遍历一边（从前往后）找到相对最大和最小的点（最大点要在找到的最小点之后，卖出收益最大）

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

3.最大公共子串 

注意状态转移方程设计，同时注意dp[101][101]要一开始设置0，={0}

#include <iostream>
using namespace std;
int main() {
    string a,s1,s2;
    int l=101;
    int max1=0;
    getline(cin,a);
    for(int i=0;i<a.length();i++){        
        if(a[i]==','){
            l=i;
        }
        if(i>l){
            s2.push_back(a[i]);
        }else{
s1.push_back(a[i]);
        }
    }
    int dp[101][101]={0};

    for(int i=1;i<=s1.length();i++){
        for(int j=1;j<=s2.length();j++){
            if(s1[i-1]==s2[j-1]){
            dp[i][j]=dp[i-1][j-1]+1;
            max1=max(dp[i][j],max1);
            }
        }
    }
cout<<max1;
    return 0;
}

4.打家劫舍

主要就是考虑隔开一个的情况，dp[i]=max(dp[i-1],dp[i-2]+nums[i]); 隔开就是减2

class Solution {
public:
    int rob(vector<int>& nums) {
        int l=nums.size();
       
        if(l==1){
            return nums[0];
        }   

        int dp[101]={0};
        dp[0]=nums[0];
        dp[1]=max(dp[0],nums[1]);
        int max1=dp[1];
        for(int i=2;i<l;i++){
            dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
            max1=max(max1,dp[i]);
        }
        return max1;
    }
};