代码随想录算法训练52 | 动态规划part13

?300.最长递增子序列?

今天开始正式子序列系列，本题是比较简单的，感受感受一下子序列题目的思路。?

视频讲解：动态规划之子序列问题，元素不连续！| LeetCode：300.最长递增子序列_哔哩哔哩_bilibili

代码随想录

• dp[i]表示以nums[i]结尾的最长递增子序列的长度。
• 递推公式：循环遍历所有i之前的j，若nums[i]>nums[j]，则取dp[i]=max(dp[j]+1,dp[i])dp[i]=max(dp[j]+1,dp[i])dp[i]=max(dp[j]+1,dp[i]);
• 初始化：dp[i]=1
• 遍历顺序：外层循环从前向后，内层循环无所谓

代码：

// 最长递增子序列
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.size() <= 1) return nums.size();
        vector<int> dp(nums.size(), 1); // 初始化：dp[i]=1
        int result = 0;
        // 循环遍历所有i之前的j
        for (int i = 1; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
       
                //  位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值
                //  dp[i]表示以nums[i]结尾的最长递增子序列的长度
                if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
                
            }
            if (dp[i] > result) result = dp[i];
        }
        return result;
    }
};

?674.?最长连续递增序列?

本题相对于昨天的动态规划：300.最长递增子序列?最大的区别在于“连续”。?先尝试自己做做，感受一下区别??

视频讲解：动态规划之子序列问题，重点在于连续！| LeetCode：674.最长连续递增序列_哔哩哔哩_bilibili

代码随想录

?718.?最长重复子数组?

稍有难度，要使用二维dp数组了

视频讲解：动态规划之子序列问题，想清楚DP数组的定义 | LeetCode：718.最长重复子数组_哔哩哔哩_bilibili

代码随想录