30. 最长数对链（Medium）
题目链接
解题思路
本题要求在数对数组中挑选一些数对，组成一个呈现上升形态的最长数对链。这可以转化为「最长递增子序列」模型。
与整数数组的区别在于，使用动态规划之前应先对数组排序。计算 dp[i] 时，需要知道所有左区间比 pairs[i] 的左区间小的链对。排序后只需往前遍历一遍即可。
- 状态表示：dp[i] 表示以 i 位置的数对为结尾时，最长数对链的长度。
- 状态转移方程：对于 dp[i]，遍历 [0, i-1] 区间内数对下标 j，找出所有满足 pairs[j][1] < pairs[i][0] 的 j。取其中最大的 dp[j] 加上 1，即为以 i 位置为结尾的最长数对链。
- 初始化：全部初始化为 1。
- 填表顺序：从左往右。
- 返回值：返回整个 dp 表中的最大值。
C++ 代码实现
class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
sort(pairs.begin(), pairs.end()); // 升序
int n = pairs.size();
vector<int> dp(n, 1);
int res = 1;
for(int i = 1; i < n; i++) {
for(int j = 0; j < i; j++) {
if(pairs[i][0] > pairs[j][1]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
res = max(res, dp[i]);
}
return res;
}
};
31. 最长定差子序列（Medium）
题目链接
解题思路
本题与「最长递增子序列」相似，但 arr.length 高达 10^5，O(N^2) 的 LCS 模型会超时。利用定差信息，可以用数值来定义 dp 数组的值，形成状态转移。
- 状态表示：dp[i] 表示以 i 位置的元素为结尾的所有子序列中，最长的等差子序列的长度。
- 状态转移方程：对于 dp[i]，上一个定差子序列的取值定为 arr[i] - difference。找到以上一个数字为结尾的定差子序列长度的 dp[arr[i] - difference]，然后加上 1。 此处可使用哈希表优化，将「元素，dp[j]」绑定放入哈希表中，甚至不创建 dp 数组，直接在哈希表中做动态规划。
- 初始化：第一个元素放进哈希表中，hash[arr[0]] = 1。
- 填表顺序：从左往右。
- 返回值：返回整个 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）
题目链接
解题思路
- 状态表示：仅知道以 i 结尾无法确定斐波那契序列的样子。根据特性，仅需知道序列里面最后两个元素即可确定。修改状态表示为：dp[i][j] 表示以 i 位置以及 j 位置的元素为结尾的所有子序列中，最长的斐波那契子序列的长度。规定 i < j。
- 状态转移方程：设 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 之前，将所有「元素 + 下标」绑定在一起放到哈希表中。
- 初始化：可以将表里面的值都初始化为 2。
- 填表顺序：先固定最后一个数，然后枚举倒数第二个数。
- 返回值：返回 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）
题目链接
解题思路
- 状态表示：dp[i][j] 表示以 i 位置以及 j 位置的元素为结尾的所有子序列中，最长的等差序列的长度。规定 i < j。
- 状态转移方程：设 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 一边保存，遍历顺序先固定倒数第二个数，再遍历倒数第一个数。
- 初始化：根据实际情况，可以将所有位置初始化为 2。
- 填表顺序：先固定倒数第二个数，然后枚举倒数第一个数。
- 返回值：返回 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
解题思路
- 状态表示：dp[i][j] 表示以 i 位置以及 j 位置的元素为结尾的所有子序列中，等差子序列的个数。规定 i < j。
- 状态转移方程：设 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>>存储重复值的下标。
- a 存在且下标为 k：dp[i][j] += dp[k][i] + 1。因为 a 可能有很多个，需要全部累加。
优化点：由于要统计个数，需保存下标数组。使用
- 初始化：初始化 dp 表为 0。
- 填表顺序：先固定倒数第一个数，然后枚举倒数第二个数。
- 返回值：返回 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）
题目链接
解题思路
可以先预处理一下，将所有子串「是否回文」的信息统计在 dp 表里面，然后直接在表里面统计 true 的个数即可。
- 状态表示：创建一个 n * n 的二维 dp 表，只用到「上三角部分」。dp[i][j] 表示 s 字符串 [i, j] 的子串，是否是回文串。
- 状态转移方程：分析区间两头的元素。
- 当 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]。
- 初始化：无需特殊初始化。
- 填表顺序：从下往上填写每一行，每一行的顺序无所谓。
- 返回值：返回 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）
题目链接
解题思路
- 先用 dp 表统计出「所有子串是否回文」的信息。
- 然后根据 dp 表 true 的位置，得到回文串的「起始位置」和「长度」。
- 在表中找出最长回文串。
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);
}
};
