代码随想录算法训练营 ---第五十二天

第一题：

简介：

动态规划五部曲：

1.确定 dp数组下标的定义

dp[i] 到达 i 时最长递增子序列的长度

2.确定递推公式

我们确定当前的最大长度需要遍历前面所有的最大长度，然后如果序列最后一个值小于nums[i]那就dp[j] + 1；然后不断遍历保持最大。

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

3.初始化dp数组

vector<int> dp(nums.size(), 1);

因为一个数也是一个递增序列

4.确定遍历顺序

 for (int i = 1; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
            }
            if (dp[i] > result) result = dp[i]; // 取长的子序列
        }

5.打印数组

代码实现：

  int lengthOfLIS(vector<int>& nums) {
       if (nums.size() <= 1) return nums.size();
        vector<int> dp(nums.size(), 1);
        int result = 0;
        for (int i = 1; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
            }
            if (dp[i] > result) result = dp[i]; // 取长的子序列
        }
        return result;
       }

第二题：

简介：

大家可以看一看第一题与第二题大的不同之处。第二题新增了一个条件：必须是连续的。所以，我们不需要去遍历数组去得到从前最大的子串长度。因为是连续的所以我们只需要知道前一个数是否小于当前数。所以递推公式为：

其他与第一题相同。

代码实现：

   int findLengthOfLCIS(vector<int>& nums) {
        if (nums.size() <= 1) return nums.size();
        vector<int> dp(nums.size(), 1);
        int result =0;
        for(int i = 1; i < nums.size(); i++){
           if(nums[i]>nums[i-1])dp[i] = dp[i-1]+1;
           if(dp[i]>result)result =dp[i];
        }
        return result;
    }

第三题：

简介：

本题先看实例图：

一个二维数组dp[i][j]进行循环遍历，如果遇到相等值就让左上角的值加一赋给当前值，但是为什么要左上角加一赋值，因为我们可以在脑中想想如果两个完全相同的数组组成二维数组，把列和行值相同的交接处值为1，其他为零。把1连接起来是不是一条从左上到右下的对角线所以：最长重复子数组它的值dp[i][j]是由dp[i-1][j-1]计算而出的所以递推公式为：

  if(nums1[i-1]==nums2[j-1]) dp[i][j] = dp[i-1][j-1]+1;

如果两值相等就让dp[i-1][j-1]加一。

动态规划五部曲：

1.确定 dp数组下标的定义

dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。

2.确定递推公式

if(nums1[i-1]==nums2[j-1]) dp[i][j] = dp[i - 1][j - 1] + 1;;

3.初始化dp数组

都初始化为零。

4.确定遍历顺序

 for(int i=1;i<=nums1.size();i++){
           for(int j=1;j<=nums2.size();j++){
               if(nums1[i-1]==nums2[j-1]) dp[i][j] = dp[i-1][j-1]+1;
               if(dp[i][j]>result) result =dp[i][j];
           }
       }

5.打印数组

代码实现：

    int findLength(vector<int>& nums1, vector<int>& nums2) {
       vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,0));
       dp[0][0] =0;
       int result;
       for(int i=1;i<=nums1.size();i++){
           for(int j=1;j<=nums2.size();j++){
               if(nums1[i-1]==nums2[j-1]) dp[i][j] = dp[i-1][j-1]+1;
               if(dp[i][j]>result) result =dp[i][j];
           }
       }
       return result;
    }