代码随想录day43 动态规划10

300.最长递增子序列

思路:dp【i】需要一点点推，从前往后，而且需要遍历i之前的每一个，才能确定。

什么时候子序列可以加上dp【i】：当num【i】比num【j】大的时候。

需要双层循环，且i在外层

注意：

五部：

1.dp[i]:以nums【i】结尾的，最长子序列的长度

2.  if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

3.  dp[0]=1;

4.

代码：

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n=nums.size();
        if(n==1)return 1;
        vector<int>dp(n,1);
        int res=0;
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){//如果nums[i]可以接在j后面。
                    dp[i]=max(dp[i],dp[j]+1);
                }
            }
            if(dp[i]>res)res=dp[i];
        }
        return res;
    }
};

674. 最长连续递增序列

法1：贪心：

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

法2：dp

思路:遍历一次即可，只要比上一个大就=上一个再加1；并设置最大值，每次比较。

注意：

代码：

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

718. 最长重复子数组

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int n1=nums1.size();
        int n2=nums2.size();
        int res=0;
        vector<vector<int>>dp(n1+1,vector<int>(n2+1,0));
        for(int i=1;i<=n1;i++){
            for(int j=1;j<=n2;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;
    }
};