基本题目

300. 最长上升子序列

动态规划：根据之前所有更小的元素调整 dp 数值

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

贪心思想：为了让序列更长，我们需要让最后添加的数尽可能的小。每次读取一个元素时，我们可以考虑以它为结尾最长的符合条件的子序列，用它去替换之前得到的等长子序列。这样新的子序列的末尾元素会更小，可能在未来容纳更多的元素

正确性证明：如果末尾元素更大，那么将它添加到原来的等长子序列之后，可以得到更长的子序列

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size(), len = 1;
        vector<int> lastVal(n + 1, INT_MIN);
        lastVal[1] = nums[0];

        for (int i = 0; i < n; i++) {
            if (nums[i] > lastVal[len]) {
                lastVal[len + 1] = nums[i];
                len++;
            }
            else {
                auto it = lower_bound(lastVal.begin(), lastVal.begin() + len, nums[i]);
                *it = nums[i];
            }
        }

        return len;
    }
};

1143. 最长公共子序列

动态规划：前 i 个字符和前 j 个字符的比较

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n = text1.size(), m = text2.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; 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[n][m];
    }
};

1035. 不相交的线

与最长公共子序列完全等价

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), m = nums2.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (nums1[i - 1] == nums2[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[n][m];
    }
};

674. 最长连续递增序列

动态规划：如果更大则等于前一数值加 1，否则等于 1。可以滚动数组优化

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int run = 0, prev = INT_MIN, maxRun = 0;
        for (const int &num : nums) {
            if (num > prev) run++;
            else {
                maxRun = max(run, maxRun);
                run = 1;
            }
            prev = num;
        }
        return max(run, maxRun);
    }
};

718. 最长重复子数组

动态规划：如果元素匹配，则 dp[i][j] = dp[i-1][j-1] + 1，否则为 0

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), m = nums2.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        int maxLen = 0;

        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (nums1[i] == nums2[j]) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                    maxLen = max(maxLen, dp[i + 1][j + 1]);
                }

        return maxLen;
    }
};

每一个重复子数组实际上对应了一种数组对齐的方式，因此可以采用滑动数组的方式求解

这种方法本质上是利用了状态转移函数的特点：只依赖于同一对角线上的元素。滑动数组的方式实际上就是遍历所有的对角线，省略的 dp 数组的空间分配

class Solution {
public:
    int maxLength(vector<int> &nums1, vector<int> &nums2, int offset) {
        int i = offset > 0 ? offset : 0;
        int j = offset > 0 ? 0 : -offset;
        int maxLen = 0, run = 0;
        while (i < nums1.size() && j < nums2.size()) {
            if (nums1[i++] == nums2[j++]) run++;
            else {
                maxLen = max(maxLen, run);
                run = 0;
            }
        }
        return max(maxLen, run);
    }

    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int maxLen = 0, n = nums1.size(), m = nums2.size();
        for (int offset = -m + 1; offset < n; offset++) {
            if (n - offset < maxLen) break;
            maxLen = max(maxLength(nums1, nums2, offset), maxLen);
        }
        return maxLen;
    }
};

53. 最大子序和

动态规划：以此为末尾元素的最大子序和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int curr = 0, max = INT_MIN, n = nums.size();
        for (const int n : nums) {
            curr = curr > 0 ? curr + n : n;
            if (curr > max) max = curr;
        }
        return max;
    }
};

贪心算法的解法参考[[10. 贪心算法（1）#53. 最大子序和]]

392. 判断子序列

双指针/动态规划：匹配时考虑下一个

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int m = s.size(), n = t.size();
        int i = 0, j = 0;
        while (i < m && j < n) {
            if (t[j] == s[i]) i++;
            j++;
        }
        return i == m;
    }
};

如果匹配串较多：可以统计每个位置之后各个字母首次出现的位置

115. 不同的子序列

动态规划：考虑前 i 个和前 j 个构成的字串的匹配数目

class Solution {
public:
    int numDistinct(string s, string t) {
        int n = s.size(), m = t.size();
        if (n < m) return 0;

        // s[0..i) and t[0..j)
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        for (int i = 0; i <= n; i++) dp[i][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= min(i, m); j++) {
                dp[i][j] = dp[i - 1][j];
                if (s[i - 1] == t[j - 1]) dp[i][j] += dp[i - 1][j - 1];
            }
        }
        return dp[n][m];
    }
};

583. 两个字符串的删除操作

动态规划：与编辑距离类似，去掉替换操作

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

        for (int i = 0; i <= n; i++) dp[i][0] = i;
        for (int j = 1; j <= m; j++) dp[0][j] = j;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (word1[i - 1] == word2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
            }
        }
        return dp[n][m];
    }
};

72. 编辑距离

动态规划：考虑前 i 个和前 j 个构成的字串的编辑距离

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

        for (int i = 0; i <= n; i++) dp[i][0] = i;
        for (int j = 1; j <= m; j++) dp[0][j] = j;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (word1[i - 1] == word2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
            }
        }
        return dp[n][m];
    }
};

647. 回文子串

动态规划：由于只取决于对角线相邻元素，因此可以修改遍历方式，滚动数组优化

class Solution {
public:
    int countSubstrings(string s) {
        int count = 1, n = s.size();
        int p, q;
        for (int i = 1; i < n; i++) {
            p = i, q = i;
            do {
                if (s[p] == s[q]) count++;
                else break;
            } while (--p >= 0 && ++q < n);
            p = i - 1, q = i;
            do {
                if (s[p] == s[q]) count++;
                else break;
            } while (--p >= 0 && ++q < n);
        }
        return count;
    }
};

回文子串还可以使用 Manacher 方法求解，利用已经探测到的中心对称信息来加速探测过程

516. 最长回文子序列

动态规划：考察 s[i..j] 子串的最长回文子序列，根据首尾字符是否相同进行转移

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