LeetCode 动态规划L1

开二维数组dp[][] 且i与j下标都从1开始：

vector<vector<int>>dp(len1+1,vector<int>(len2+1,0));

53. 连续数组最大子序和

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

状态转移考虑dp[i][0/1],对于第i个状态时对该物品，选还是不选
当dp[i][0]时，dp[i][0]可以由dp[i-1][0]或者dp[i-1][1]转移
当dp[i][1]时，dp[i][1]仅可由dp[i-1][0]+w[i]
优化到一维
状态转移考虑dp[0/1],对于第i个状态时对该物品，选还是不选
当dp[0]时，dp[0]可以由dp[0]或者dp[1]转移
当dp[1]时，dp[1]仅可由dp[0]+w[i]

1025. 除数博弈

f[i] 表示当前数字 i 的时候先手是处于必胜态还是必败态，true表示先手必胜，false表示先手必败，从前往后递推，根据我们上文的分析，枚举 i 在 (0, i)中 i的因数 j，看是否存在 f[i-j]为必败态，若存在必败状态，直接使bob转移到必败态即可

121. 买卖股票的最佳时机

dp[i]表示i时刻得到的最大收益，那么dp[i]=max(dp[i-1],price[i]-premin)不卖与卖

1143. 最长公共子序列

if(text1[i-1]==text2[j-1])//手动滑稽，text文本串下标还是从0开始的
    dp[i][j]=dp[i-1][j-1]+1;
else
    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

class Solution {
public:
    bool isSubsequence(string s, string t) {
        //双指针问题
        int i=0,j=0;
        int n=s.size(),m=t.size();
        while(i<n&&j<m)
        {
            if(s[i]==t[j]) i++;
            j++;
        }
        if(i==n)
            return true;
        else 
            return false;
    
    }
};

LeetCode 动态规划L1