代码随想录算法训练营day48|动态规划10

最长递增子序列

dp[i]是以元素i为结尾的递增子序列的长度最大值，如果nums[i]>nums[j],则i的递增子序列的长度可以是dp[j]+1,取max，dp[i]就等于max（dp[i],dp[j]+1)

注意这里必须要有if (nums.size() <= 1) return nums.size();，因为result初始化为0了，但实际只有一个元素时也是1

class Solution {
public: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;}
};

最长连续递增子序列

因为是连续的，所以只用比较dp[i-1]和dp[i]的，反而更简单了

最长重复子数组

本题需要用到二维dp数组
确定dp数组（dp table）以及下标的含义
dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。 （特别注意： “以下标i - 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串 ）

用滚动一维数组来优化

class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {vector<int> dp(vector<int>(nums2.size()+1,0));//为什么以nums2初始化，因为nums2是行大小int result=0;for(int i=1;i<=nums1.size();i++){for(int j=nums2.size();j>0;j--){if(nums1[i-1]==nums2[j-1]){dp[j]=dp[j-1]+1;}else dp[j]=0;//因为是从后往前，所以会有一个赋0的操作if(dp[j]>result) result=dp[j];}}return result;}
};