首页 计算机科学 算法 LeetCode

# 最长递增子序列

题目链接🔗

  1. 确定 dp 数组以及下标的含义

dp [i]: 表示 i 之前 (包括 i) 的以 nums [i] 结尾的最长递增子序列长度。

  1. 确定递推公式

位置 i 的最长升序子序列等于 j (0 到 i-1) 各个位置的最长升序子序列 + 1 的最大值。

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

  1. dp 数组的初始化

每一个 i，对应的 dp [i]（即最长递增子序列）起始大小至少都是 1.

  1. 确定遍历顺序

dp [i] 是有 0 到 i-1 各个位置的最长递增子序列 推导而来，那么遍历 i 一定是从前向后遍历。

j 是遍历 0 到 i-1。从前到后，还是从后到前遍历都无所谓，默认从前向后遍历。

  1. 举例推导 dp 数组

Alt text

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;
    }
};

# 最长连续递增子序列

题目链接🔗

  1. 确定 dp 数组以及下标的含义

dp [i]：以下标 i 为结尾 (起始位置不一定是 0) 的连续递增的子序列长度为 dp [i]。

  1. 确定递推公式

如果 nums[i] > nums[i - 1] ，那么以 i 为结尾的连续递增的子序列长度一定等于以 i - 1 为结尾的连续递增的子序列长度 + 1 。

dp[i]=dp[i−1]+1dp[i] = dp[i - 1] + 1

  1. dp 数组如何初始化

以下标 i 为结尾的连续递增的子序列长度最少也应该是 1，所以 dp [i] 应该初始 1。

  1. 确定遍历顺序

从递推公式上可以看出， dp [i + 1] 依赖 dp [i]，所以一定是从前向后遍历。

  1. 举例推导 dp 数组

Alt text

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        int result = 1;
        vector<int> dp(nums.size() ,1);
        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;
    }
};

# 最长连续子数组

题目链接🔗

子数组指的是连续子数组。

本题是动规解决的经典题目，只要想到用二维数组可以记录两个字符串的所有比较情况，这样就比较好推递推公式了。

  1. 确定 dp 数组以及下标的含义

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

不表示以下标 i 和 j 结尾是因为

  1. 确定递推公式

根据 dp [i][j] 的定义，dp [i][j] 的状态只能由 dp [i - 1][j - 1] 推导出来。

当 A [i - 1] 和 B [j - 1] 相等的时候：$$dp [i][j] = dp [i - 1][j - 1] + 1$$

  1. dp 数组如何初始化

为了方便递推公式，dp [i][0] = dp [0][j] = 0。

  1. 确定遍历顺序

外层 for 循环遍历 A，内层 for 循环遍历 B。都从 1 开始向后遍历。

  1. 举例推导 dp 数组

Alt text

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

# 最长公共子序列

题目链接🔗

  1. 确定 dp 数组以及下标的含义

dp [i][j]: [0, i - 1] 范围的字符串 text1 与 [0, j - 1] 范围的字符串 text2 的公共子序列最长为 dp [i][j]。

  1. 确定递推公式

主要就是两大情况：

  • if text1[i - 1] == text2[j - 1] ，那么找到了一个公共元素，所 p [i][j] = dp [i - 1][j - 1] + 1;

  • if text1[i - 1] != text2[j - 1] ，那就看看 text1 [0, i - 2] 与 text2 [0, j - 1] 的最长公共子序列 和 text1 [0, i - 1] 与 text2 [0, j - 2] 的最长公共子序列，取最大的。dp [i][j] = max (dp [i - 1][j], dp [i][j - 1]);

  1. dp 数组如何初始化

test1 [0, i-1] 和空串的最长公共子序列自然是 0，所以 dp [i][0] = 0，同理 dp [0][j] 也是 0。

其他下标都是随着递推公式逐步覆盖，初始为多少都可以。

  1. 确定遍历顺序

从前向后，从上到下来遍历。

  1. 举例推导 dp 数组

Alt text

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
        for (int i = 1; i <= text1.size(); i++) {
            for (int j = 1; j <= text2.size(); j++) {
                if (text1[i - 1] == text2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[text1.size()][text2.size()];
    }
};