C++算法
动态规划经典题型：最长数对链与回文子串
通过七个 LeetCode 动态规划例题，讲解最长数对链、定差子序列、斐波那契子序列、等差数列及回文子串等问题的解法。涵盖状态定义、转移方程推导及 C++ 代码实现，重点分析哈希表优化与二维 DP 填表顺序。
通过七个 LeetCode 动态规划例题，讲解最长数对链、定差子序列、斐波那契子序列、等差数列及回文子串等问题的解法。涵盖状态定义、转移方程推导及 C++ 代码实现，重点分析哈希表优化与二维 DP 填表顺序。
本题要求在数对数组中挑选一些数对，组成一个呈现上升形态的最长数对链。这可以转化为「最长递增子序列」模型。
与整数数组的区别在于，使用动态规划之前应先对数组排序。计算 dp[i] 时，需要知道所有左区间比 pairs[i] 的左区间小的链对。排序后只需往前遍历一遍即可。
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;
}
};
本题与「最长递增子序列」相似，但 arr.length 高达 10^5，O(N^2) 的 LCS 模型会超时。利用定差信息，可以用数值来定义 dp 数组的值，形成状态转移。
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;
}
};
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;
}
};
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;
}
};
unordered_map<long long, vector<int>> 存储重复值的下标。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;
}
};
可以先预处理一下，将所有子串「是否回文」的信息统计在 dp 表里面，然后直接在表里面统计 true 的个数即可。
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;
}
};
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);
}
};
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online