动态规划经典题型：最长数对链与回文子串

31. 最长定差子序列（Medium）

题目链接

1218. 最长定差子序列 - LeetCode

解题思路

本题与「最长递增子序列」相似，但 arr.length 高达 10^5，O(N^2) 的 LCS 模型会超时。利用定差信息，可以用数值来定义 dp 数组的值，形成状态转移。

1. 状态表示：dp[i] 表示以 i 位置的元素为结尾的所有子序列中，最长的等差子序列的长度。
2. 状态转移方程：对于 dp[i]，上一个定差子序列的取值定为 arr[i] - difference。找到以上一个数字为结尾的定差子序列长度的 dp[arr[i] - difference]，然后加上 1。 此处可使用哈希表优化，将「元素，dp[j]」绑定放入哈希表中，甚至不创建 dp 数组，直接在哈希表中做动态规划。
3. 初始化：第一个元素放进哈希表中，hash[arr[0]] = 1。
4. 填表顺序：从左往右。
5. 返回值：返回整个 dp 表中的最大值。

C++ 代码实现

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        unordered_map<int,int> hash;
        int n = arr.size();
        int ret = 1;
        for(int i = 0; i < n; i++) {
            hash[arr[i]] = hash[arr[i] - difference] + 1; // 没有解相当于初始化为 1
            ret = max(ret, hash[arr[i]]);
        }
        return ret;
    }
};

32. 最长的斐波那契子序列的长度（Medium）

题目链接

873. 最长的斐波那契子序列的长度 - LeetCode

解题思路

1. 状态表示：仅知道以 i 结尾无法确定斐波那契序列的样子。根据特性，仅需知道序列里面最后两个元素即可确定。修改状态表示为：dp[i][j] 表示以 i 位置以及 j 位置的元素为结尾的所有子序列中，最长的斐波那契子序列的长度。规定 i < j。
2. 状态转移方程：设 nums[i] = b, nums[j] = c，则前一个元素 a = c - b。
   • a 存在且下标 k 满足 a < b：dp[i][j] = dp[k][i] + 1。
   • a 存在但 b < a < c：dp[i][j] = 2。
   • a 不存在：dp[i][j] = 2。 优化点：在 dp 之前，将所有「元素 + 下标」绑定在一起放到哈希表中。
3. 初始化：可以将表里面的值都初始化为 2。
4. 填表顺序：先固定最后一个数，然后枚举倒数第二个数。
5. 返回值：返回 dp 表中的最大值 ret。若 ret < 3，说明不存在，返回 0。

C++ 代码实现

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        int n = arr.size();
        vector<vector<int>> dp(n, vector<int>(n, 2));
        int ret = 2;
        for(int j = 2; j < n; j++) {
            int pre = 0, i = j - 1;
            while(pre < i) {
                int sum = arr[pre] + arr[i];
                if(sum == arr[j]) {
                    dp[i][j] = dp[pre][i] + 1;
                    ret = max(ret, dp[i][j]);
                    i--;
                }
                if(sum > arr[j]) i--; // 范围缩小
                if(sum < arr[j]) pre++; // arr[pre] 小了
            }
        }
        return (ret < 3) ? 0 : ret;
    }
};

33. 最长等差数列（Medium）

题目链接

1027. 最长等差数列 - LeetCode

解题思路

1. 状态表示：dp[i][j] 表示以 i 位置以及 j 位置的元素为结尾的所有子序列中，最长的等差序列的长度。规定 i < j。
2. 状态转移方程：设 nums[i] = b, nums[j] = c，则前一个元素 a = 2 * b - c。
   • a 存在且下标 k 满足 a < b：dp[i][j] = dp[k][i] + 1。这里因为会有许多个 k，仅需离 i 最近的 k 即可。
   • a 存在但 b < a < c：dp[i][j] = 2。
   • a 不存在：dp[i][j] = 2。 优化点：使用哈希表保存元素及其最近的下标。一边 dp 一边保存，遍历顺序先固定倒数第二个数，再遍历倒数第一个数。
3. 初始化：根据实际情况，可以将所有位置初始化为 2。
4. 填表顺序：先固定倒数第二个数，然后枚举倒数第一个数。
5. 返回值：返回 dp 表中的最大值。

C++ 代码实现

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        unordered_map<int,int> mp;
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(n, 2));
        int ret = 2;
        for(int j = 0; j < n; j++) {
            for(int i = j + 1; i < n; i++) {
                int a = 2 * nums[j] - nums[i];
                if(mp.count(a)) {
                    dp[j][i] = dp[mp[a]][j] + 1;
                }
                ret = max(ret, dp[j][i]);
            }
            mp[nums[j]] = j;
        }
        return ret;
    }
};

34. 等差数列划分 II - 子序列（Hard）

题目链接

446. 等差数列划分 II - 子序列 - LeetCode

解题思路

1. 状态表示：dp[i][j] 表示以 i 位置以及 j 位置的元素为结尾的所有子序列中，等差子序列的个数。规定 i < j。
2. 状态转移方程：设 nums[i] = b, nums[j] = c，则前一个元素 a = 2 * b - c。
   • a 存在且下标为 k：dp[i][j] += dp[k][i] + 1。因为 a 可能有很多个，需要全部累加。 优化点：由于要统计个数，需保存下标数组。使用 unordered_map<long long, vector<int>> 存储重复值的下标。
3. 初始化：初始化 dp 表为 0。
4. 填表顺序：先固定倒数第一个数，然后枚举倒数第二个数。
5. 返回值：返回 dp 表中所有元素的和。

C++ 代码实现

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        unordered_map<long long, vector<int>> hash;
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        int ret = 0;
        for(int i = 0; i < n; i++) {
            for(int j = i + 1; j < n; j++) {
                long long a = (long long)2 * nums[i] - nums[j];
                if(hash.count(a)) {
                    for(int ch : hash[a]) {
                        dp[i][j] += dp[ch][i] + 1;
                    }
                }
                ret += dp[i][j];
            }
            hash[nums[i]].push_back(i);
        }
        return ret;
    }
};

35. 回文子串（Medium）

题目链接

647. 回文子串 - LeetCode

解题思路

可以先预处理一下，将所有子串「是否回文」的信息统计在 dp 表里面，然后直接在表里面统计 true 的个数即可。

1. 状态表示：创建一个 n * n 的二维 dp 表，只用到「上三角部分」。dp[i][j] 表示 s 字符串 [i, j] 的子串，是否是回文串。
2. 状态转移方程：分析区间两头的元素。
   • 当 s[i] != s[j] 的时候：不可能是回文串，dp[i][j] = false。
   • 当 s[i] == s[j] 的时候：
     • 长度为 1（i == j）：一定是回文串，dp[i][j] = true。
     • 长度为 2（i + 1 == j）：一定是回文串，dp[i][j] = true。
     • 长度大于 2：看 [i+1, j-1] 区间的子串是否回文：dp[i][j] = dp[i+1][j-1]。
3. 初始化：无需特殊初始化。
4. 填表顺序：从下往上填写每一行，每一行的顺序无所谓。
5. 返回值：返回 dp 表中 true 的个数。

C++ 代码实现

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n));
        int ret = 0;
        for(int i = n - 1; i >= 0; i--) {
            for(int j = i; j < n; j++) {
                if(s[i] == s[j]) dp[i][j] = (i + 1 < j) ? dp[i + 1][j - 1] : true;
                if(dp[i][j]) ret++;
            }
        }
        return ret;
    }
};

36. 最长回文子串（Medium）

题目链接

5. 最长回文子串 - LeetCode

解题思路

1. 先用 dp 表统计出「所有子串是否回文」的信息。
2. 然后根据 dp 表 true 的位置，得到回文串的「起始位置」和「长度」。
3. 在表中找出最长回文串。

C++ 代码实现

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n));
        int len = 1, begin = 0;
        for(int i = n - 1; i >= 0; i--) {
            for(int j = i; j < n; j++) {
                if(s[i] == s[j]) dp[i][j] = (i + 1 < j) ? dp[i + 1][j - 1] : true;
                if(dp[i][j] && j - i + 1 > len) {
                    len = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substr(begin, len);
    }
};