C++ snippets
ostream& operator<<(ostream& os, const vector<int>& v) {
for (auto i : v) os << i << " ";
return os << endl;
}
ostream& operator<<(ostream& os, const vector<vector<int>>& v) {
for (auto i : v) os << i;
return os;
}
入门
[Overlapping Subproblems Property in Dynamic Programming DP-1 - GeeksforGeeks](https://www.geeksforgeeks.org/overlapping-subproblems-property-in-dynamic-programming-dp-1/);
-
剑指 Offer 10- I. 斐波那契数列 - 力扣（LeetCode）;
class Solution { public: int fib(int n) { const int MOD = 1e9 + 7; int a{}, b{1}; for (int i{}; i < n; ++i) tie(a, b) = pair(b, a % MOD + b % MOD); return a % MOD; } }; // 玩个骚的 class Solution { public: int fib(int n) { int a{}, b{1}; while (n--) tie(a, b) = pair{b, (a + b) % 1000000007}; return a % 1000000007; } }; -
vector<int> a(31, -1); class Solution { public: int fib(int n) { if (a[n] == -1) { if (n <= 1) a[n] = n; else a[n] = fib(n - 1) + fib(n - 2); } return a[n]; } }; // 滚动数组优化 class Solution { public: int fib(int n) { int a{}, b{1}; for (int i{}; i < n; ++i) { int tmp = b; b += a; a = tmp; } return a; } }; -
70. 爬楼梯 - 力扣（LeetCode）;剑指 Offer 10- II. 青蛙跳台阶问题
class Solution { public: int climbStairs(int n) { if (n < 3) return n; vector<int> dp(n); dp[0] = 1, dp[1] = 2; for (int i{2}; i < n; ++i) dp[i] = dp[i - 1] + dp[i - 2]; return dp[n - 1]; } }; // 滚动数组 class Solution { public: int climbStairs(int n) { if (n < 3) return n; int a{1}, b{2}; for (int i{2}; i < n; ++i) tie(a, b) = pair(b, a + b); return b; } }; // 终极优化 class Solution { public: int climbStairs(int n) { if (n < 3) return n; int a{1}, b{2}, tmp{}; for (int i{2}; i < n; ++i) tmp = b, b += a, a = tmp; return b; } }; -
746. 使用最小花费爬楼梯 - 力扣（LeetCode）;剑指 Offer II 088. 爬楼梯的最少成本 - 力扣（LeetCode）;
class Solution { public: int minCostClimbingStairs(vector<int> &cost) { int n = cost.size(); vector<int> dp(n + 1); for (int i{2}; i <= n; ++i) dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]); return dp[n]; } }; // 滚动数组 class Solution { public: int minCostClimbingStairs(vector<int> &cost) { int n = cost.size(), a{}, b{}, tmp{}; for (int i{}; i < n - 1; ++i) tmp = b, b = min(b + cost[i + 1], a + cost[i]), a = tmp; return b; } }; -
343. 整数拆分 - 力扣（LeetCode）;(还有$O(1)$的数学做法)
class Solution { public: int integerBreak(int n) { vector<int> dp(n + 1); dp[2] = 1; for (int i{3}; i <= n; ++i) // 这里进行了优化, 原来是j<i, 浪费时间 // 优化的依据是满足最大乘积的拆分数字尽可能接近 for (int j{1}; j < 1 + i / 2; ++j) dp[i] = max({dp[i], j * dp[i - j], j * (i - j)}); return dp[n]; } };
路径问题
-
62. 不同路径 - 力扣（LeetCode）;(经典的二维DP问题)
class Solution { public: int uniquePaths(int m, int n) { vector<vector<int>> dp(m, vector<int>(n)); for (int i{}; i < n; ++i) dp[0][i] = 1; for (int j{1}; j < m; ++j) dp[j][0] = 1; for (int i{1}; i < m; ++i) for (int j{1}; j < n; ++j) dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; return dp[m - 1][n - 1]; } };滚动数组优化:
class Solution { public: int uniquePaths(int m, int n) { vector<int> dp(n, 1); for (int i{1}; i < m; ++i) for (int j{1}; j < n; ++j) dp[j] += dp[j - 1]; return dp[n - 1]; } };组合数学公式方法也可以:(注意这里
ans=ans*...是必须的, 因为如果写成ans*=...会导致除法舍入)class Solution { public: int uniquePaths(int m, int n) { long ans{1}; for (int i{}; i < m - 1; ++i) ans = ans * (n + i) / (i + 1); return ans; } }; -
63. 不同路径 II - 力扣（LeetCode）; 先写一个记忆化搜索
class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& g) { int m = g.size(), n = g[0].size(); map<pair<int, int>, int> st; // unordered_map不能用 pair 作为键 if (g[m - 1][n - 1] || g[0][0]) return 0; function<int(int, int)> f = [&](int x, int y) { int& ans = st[{x, y}]; if (ans) return ans; if (x >= m || y >= n || g[x][y]) // 有石头 return 0; if (x == m - 1 && y == n - 1) return 1; ans = f(x + 1, y) + f(x, y + 1); return ans; }; return f(0, 0); } };然后翻译成递推
class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int m = obstacleGrid.size(), n = obstacleGrid[0].size(); if (obstacleGrid[0][0]) return 0; // 注意初始值为障碍物, 后面不需要考虑 vector<vector<int>> dp(m, vector<int>(n)); int i{}, j{1}; for (; i < n && obstacleGrid[0][i] != 1; ++i) dp[0][i] = 1; for (; j < m && obstacleGrid[j][0] != 1; ++j) dp[j][0] = 1; for (i = 1; i < m; ++i) for (j = 1; j < n; ++j) if (obstacleGrid[i][j] == 0) dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; return dp[m - 1][n - 1]; } };同样可以滚动数组优化:(有点技巧, 参考了官方题解)
class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int m = obstacleGrid.size(), n = obstacleGrid[0].size(); vector<int> dp(n); dp[0] = obstacleGrid[0][0] != 1; for (int i{}; i < m; ++i) for (int j{}; j < n; ++j) { if (obstacleGrid[i][j]) { dp[j] = 0; continue; } if (j && obstacleGrid[i][j - 1] == 0) dp[j] += dp[j - 1]; } return dp[n - 1]; } }; -
剑指 Offer 47. 礼物的最大价值 - 力扣（LeetCode）;(二维dp的经典问题, 路径求和找最大即可)
class Solution { public: int maxValue(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size(); // dp vector<vector<int>> dp(m, vector<int>(n)); // init for (int i{}; i < n; ++i) dp[0][i] += grid[0][i] + (i ? dp[0][i - 1] : 0); for (int i{1}; i < m; ++i) dp[i][0] += grid[i][0] + dp[i - 1][0]; for (int i{1}; i < m; ++i) for (int j{1}; j < n; ++j) dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]; return dp[m - 1][n - 1]; } }; // 使用本地数组 class Solution { public: int maxValue(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size(); // init for (int i{1}; i < n; ++i) grid[0][i] += grid[0][i - 1]; for (int i{1}; i < m; ++i) grid[i][0] += grid[i - 1][0]; for (int i{1}; i < m; ++i) for (int j{1}; j < n; ++j) grid[i][j] = max(grid[i - 1][j], grid[i][j - 1]) + grid[i][j]; return grid[m - 1][n - 1]; } };
买卖股票系列
- 121. 买卖股票的最佳时机;剑指 Offer 63. 股票的最大利润;
class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(), mn{prices[0]}; vector<int> dp(n); for (int i{1}; i < n; ++i) { if (prices[i] < mn) mn = prices[i], dp[i] = dp[i - 1]; else dp[i] = max(dp[i - 1], prices[i] - mn); } return dp[n - 1]; } }; // 空间优化 class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(), mn{prices[0]}, ans{}, tmp{}; for (int i{1}; i < n; ++i) { if (prices[i] < mn) mn = prices[i], ans = tmp; else ans = max(tmp, prices[i] - mn); tmp = ans; } return ans; } }; -
122. 买卖股票的最佳时机 II; (贪心最快, 有利润就买卖, DP 需要考虑两种状态: 目前是否持有)
class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(), dp[n][2]; // 0 表示不持有, 1 表示持有 dp[0][0] = 0, dp[0][1] = -prices[0]; for (int i{1}; i < n; ++i) { dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]); dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]); } return dp[n - 1][0]; } }; // 滚动数组 class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(); int t0{}, t1{-prices[0]}, a0{}, a1{}; // 0 表示不持有, 1 表示持有 for (int i{1}; i < n; ++i) { a0 = max(t0, t1 + prices[i]); a1 = max(t1, t0 - prices[i]); t0 = a0, t1 = a1; } return a0; } }; -
714. 买卖股票的最佳时机含手续费;(上一题的改进版)
class Solution { public: int maxProfit(vector<int>& prices, int fee) { int n = prices.size(), ans0{}, ans1{}, t0{}, t1{}; // 0 表示不持有, 1 表示持有 t0 = 0, t1 = -prices[0]; for (int i{1}; i < n; ++i) { ans0 = max(t0, t1 + prices[i] - fee); ans1 = max(t1, t0 - prices[i]); t0 = ans0, t1 = ans1; } return ans0; } }; -
123. 买卖股票的最佳时机 III;
cpp - 188. 买卖股票的最佳时机 IV;
```cpp
```
-
给定初始资金, 买卖股票, 一个例子:
例如:初始资金M= 10000元 连续N=7天的价格分别是(单位:元)1.0, 2.0，1.0, 2.0，2.0, 3.0，2.0 最大交易次数K为2 最大收益为:50000元 注解:第一天1元买入，得10000股，第二天2元卖出得20000元，第三天1元买入， 得20000股,第六天卖出得60000元,最终盈利50000元。
#include <vector> #include <algorithm> #include <iostream> #include <cstring> using namespace std; class Solution { public: double maxProfit(double origin, vector<double>& prices, int k) { // cache + dfs // int n = prices.size(), cache[n][k+1][2]; // function<int(int, int, int)> dfs = [&](int i, int j, int hold) -> int // { // if ( i<0 ) // return hold ? -INT_MAX/2 : origin; // if ( j<0 ) // return -INT_MAX/2; // if ( cache[i][j][hold]!=-1 ) // return cache[i][j][hold]; // if ( hold ) // return cache[i][j][hold] = max(dfs(i-1, j-1, // false)/prices[i], dfs(i-1, j, true)); // return cache[i][j][hold] = max(dfs(i-1, j, true)*prices[i], // dfs(i-1, j, false)); // }; // // iteration // int n = prices.size(); // double f[n+1][k+2][2]; // memset(f, -(double)0x3f, sizeof(f)); // for ( int j=0;j<=k+1;++j ) f[0][j][false] = origin; // for ( int i=0;i<n;++i ) { // for ( int j=0;j<k+1;++j ) { // f[i+1][j+1][true] = max(f[i][j][false]/prices[i], // f[i][j+1][true]); f[i+1][j+1][false] = // max(f[i][j+1][true]*prices[i], f[i][j+1][false]); // } // } // return f[n][k+1][false]-origin; // space optimized int n = prices.size(); double f[k + 2][2]; memset(f, -(double)0x3f, sizeof(f)); for (int j = 0; j <= k + 1; ++j) f[j][false] = origin; for (int i = 0; i < n; ++i) { for (int j = k; j >= 0; --j) { f[j + 1][true] = max(f[j][false] / prices[i], f[j + 1][true]); f[j + 1][false] = max(f[j + 1][true] * prices[i], f[j + 1][false]); } } return f[k + 1][false] - origin; } }; int main(int argc, char const* argv[]) { Solution s; vector<double> v{1, 2, 1, 2, 2, 3, 2}; cout << s.maxProfit(10000, v, 2); return 0; }
打家劫舍系列
```cpp
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size(), dp[n + 1];
dp[0] = 0, dp[1] = nums[0];
for (int i{2}; i <= n; ++i) {
dp[i] = max(dp[i - 2] + nums[i - 1], dp[i - 1]);
}
return dp[n];
}
};
//
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size(), ans{nums[0]}, a{}, b{ans};
for (int i{2}; i <= n; ++i)
ans = max(a + nums[i - 1], b), a = b, b = ans;
return ans;
}
};
```
-
213. 打家劫舍 II; (考虑首尾)
cpp class Solution { public: int rob(vector<int>& nums) { auto f = [&](int l, int r) { int ans{nums[l]}, a{}, b{ans}; for (int i{l + 2}; i <= r + 1; ++i) ans = max(a + nums[i - 1], b), a = b, b = ans; return ans; }; int n = nums.size(); if (n < 2) return nums[0]; return max(f(0, n - 2), f(1, n - 1)); } }; -
337. 打家劫舍 III;
cpp -
2560. 打家劫舍 IV;
cpp
子序列/子数组
子序列
-
DP做法:
class Solution { public: int findLengthOfLCIS(vector<int>& nums) { int n = nums.size(), dp[n], ans{1}; memset(dp, 0, sizeof(dp)); dp[0] = 1; for (int i{1}; i < n; ++i) { dp[i] = dp[i - 1] + (nums[i - 1] < nums[i]); ans = max(dp[i], ans); } return ans; } };贪心也能做:(最优方法, 空间复杂度$O(1)$)
class Solution { public: int findLengthOfLCIS(vector<int>& nums) { int n = nums.size(), ans{1}, tmp{1}; for (int i{1}; i < n; ++i) { if (nums[i - 1] < nums[i]) ++tmp; else tmp = 1; ans = max(ans, tmp); } return ans; } }; -
300. 最长递增子序列 - 力扣（LeetCode）;(贪心也可以做)
class Solution { public: int lengthOfLIS(vector<int>& nums) { int n = nums.size(); vector<int> dp(n, 1); for (int i{1}; i < n; ++i) for (int j{}; j < i; ++j) if (nums[j] < nums[i]) dp[i] = max(dp[i], dp[j] + 1); return *max_element(dp.begin(), dp.end()); } }; -
1143. 最长公共子序列 - 力扣（LeetCode）;剑指 Offer II 095. 最长公共子序列 - 力扣（LeetCode）;
// 二维数组 class Solution { public: int longestCommonSubsequence(string text1, string text2) { int m = text1.size(), n = text2.size(); int dp[m + 1][n + 1]; memset(dp, 0, sizeof(dp)); for (int i{1}; i <= m; ++i) for (int j{1}; j <= n; ++j) dp[i][j] = (text1[i - 1] == text2[j - 1]) ? dp[i - 1][j - 1] + 1 : max(dp[i][j - 1], dp[i - 1][j]); return dp[m][n]; } }; // 两个数组优化 class Solution { public: int longestCommonSubsequence(string text1, string text2) { int m = text1.size(), n = text2.size(); int dp[2][n + 1]; memset(dp, 0, sizeof(dp)); for (int i{}; i < m; ++i) for (int j{}; j < n; ++j) dp[(i + 1) % 2][j + 1] = (text1[i] == text2[j]) ? dp[i % 2][j] + 1 : max(dp[(i + 1) % 2][j], dp[i % 2][j + 1]); return dp[m % 2][n]; } }; // 一维数组优化 class Solution { public: int longestCommonSubsequence(string text1, string text2) { int n = text2.size(), dp[n + 1]; memset(dp, 0, sizeof(dp)); for (char c : text1) for (int j{}, pre{}; j < n; ++j) { int tmp = dp[j + 1]; dp[j + 1] = (c == text2[j]) ? pre + 1 : max(dp[j], dp[j + 1]); pre = tmp; } return dp[n]; } }; -
1035. 不相交的线 - 力扣（LeetCode）;(和LCS类似, 转变一下思路, 直接拿来LCS的代码用)
class Solution { public: int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) { int n1 = nums1.size(), n2 = nums2.size(); int dp[n1 + 1][n2 + 1]; memset(dp, 0, sizeof(dp)); for (int i{1}; i <= n1; ++i) { for (int j{1}; j <= n2; ++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[n1][n2]; } }; -
392. 判断子序列 - 力扣（LeetCode）;(双指针也能做, DP普适性好, 编辑距离入门)
class Solution { public: bool isSubsequence(string s, string t) { int n1 = s.size(), n2 = t.size(); int dp[n1 + 1][n2 + 1]; // [0, i], [0, j]内s与t公共的子序列长度 memset(dp, 0, sizeof(dp)); for (int i{1}; i <= n1; ++i) { for (int j{1}; j <= n2; ++j) { if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1; else dp[i][j] = dp[i][j - 1]; } } return dp[n1][n2] == n1; } }; // 剪枝一下 class Solution { public: bool isSubsequence(string s, string t) { if (s.empty()) return true; // 需要考虑空字符串情况 int n1 = s.size(), n2 = t.size(); int dp[n1 + 1][n2 + 1]; // [0, i], [0, j]内s(与t公共)的子序列长度 memset(dp, 0, sizeof(dp)); for (int j{1}; j <= n2; ++j) { for (int i{1}; i <= n1; ++i) { if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1; else dp[i][j] = dp[i][j - 1]; } if (dp[n1][j] == n1) return true; } return false; } }; // 滚动数组 class Solution { public: bool isSubsequence(string s, string t) { int n1 = s.size(), n2 = t.size(); int dp[n2 + 1]; // [0, i], [0, j]内s与t公共的子序列长度 memset(dp, 0, sizeof(dp)); for (int i{1}; i <= n1; ++i) { for (int j{1}, pre{}; j <= n2; ++j) { int tmp{dp[j]}; if (s[i - 1] == t[j - 1]) dp[j] = pre + 1; else dp[j] = dp[j - 1]; pre = tmp; } } return dp[n2] == n1; } }; -
115. 不同的子序列 - 力扣（LeetCode）;剑指 Offer II 097. 子序列的数目;
class Solution { public: int numDistinct(string s, string t) { int m = s.size(), n = t.size(); int dp[m + 1][n + 1]; memset(dp, 0, sizeof(dp)); for (int i{0}; i <= m; ++i) dp[i][0] = 1; for (int i{1}; i <= m; ++i) for (int j{1}; j <= n; ++j) if (s[i - 1] == t[j - 1]) dp[i][j] = 1ll * dp[i - 1][j - 1] + dp[i - 1][j]; else dp[i][j] = dp[i - 1][j]; return dp[m][n]; } }; // 优化, 减少判断 class Solution { public: int numDistinct(string s, string t) { int n1 = s.size(), n2 = t.size(); int dp[n1 + 1][n2 + 1]; // [0, i]中t取[0, j]的子序列个数 memset(dp, 0, sizeof(dp)); for (int i{}; i <= n1; ++i) dp[i][0] = 1; for (int i{1}; i <= n1; ++i) for (int j{1}; j <= n2; ++j) dp[i][j] = 1ll * (s[i - 1] == t[j - 1]) * dp[i - 1][j - 1] + dp[i - 1][j]; return dp[n1][n2]; } }; // 滚动数组 class Solution { public: int numDistinct(string s, string t) { int m = s.size(), n = t.size(); int dp[n + 1]; memset(dp, 0, sizeof(dp)); dp[0] = 1; for (int i{1}; i <= m; ++i) for (int j{1}, pre{1}; j <= n; ++j) { // pre 初始化为1 int tmp{dp[j]}; dp[j] += 1ll * (s[i - 1] == t[j - 1]) * pre; pre = tmp; } return dp[n]; } }; -
583. 两个字符串的删除操作 - 力扣（LeetCode）;
class Solution { public: int minDistance(string s, string t) { int m = s.size(), n = t.size(); int dp[m + 1][n + 1]; // 使s[0:i]和t[0:j]相同的最少删除次数 memset(dp, 0, sizeof(dp)); // init for (int i{1}; i <= m; ++i) dp[i][0] = i; for (int i{1}; i <= n; ++i) dp[0][i] = i; // calc for (int i{1}; i <= m; ++i) for (int j{1}; j <= n; ++j) { if (s[i - 1] != t[j - 1]) // 都要删 dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1; else dp[i][j] = dp[i - 1][j - 1]; } return dp[m][n]; } }; // 滚动数组 class Solution { public: int minDistance(string s, string t) { int m = s.size(), n = t.size(), i, j, pre, tmp; int dp[n + 1]; // 使s[0:i]和t[0:j]相同的最少删除次数 memset(dp, 0, sizeof(dp)); // init for (i = 1; i <= n; ++i) dp[i] = i; // calc for (i = 1; i <= m; ++i) // dp[0] = i初始化一定要加 for (j = 1, pre = i - 1, dp[0] = i; j <= n; ++j) { tmp = dp[j]; if (s[i - 1] != t[j - 1]) // 都要删 dp[j] = min(dp[j], dp[j - 1]) + 1; else dp[j] = pre; pre = tmp; } return dp[n]; } }; -
72. 编辑距离 - 力扣（LeetCode）;(终极boss)
class Solution { public: int minDistance(string word1, string word2) { int m = word1.size(), n = word2.size(); int dp[m + 1][n + 1]; memset(dp, 0, sizeof(dp)); for (int i{1}; i <= m; ++i) dp[i][0] = i; for (int j{1}; j <= n; ++j) dp[0][j] = j; for (int i{1}; i <= m; ++i) for (int j{1}; j <= n; ++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], dp[i - 1][j - 1]}) + 1; return dp[m][n]; } }; // 一维 class Solution { public: int minDistance(string s, string t) { int m = s.size(), n = t.size(); int dp[n + 1]; memset(dp, 0, sizeof(dp)); // init for (int j{1}; j <= n; ++j) dp[j] = j; // calc for (int i{1}; i <= m; ++i) { dp[0] = i; for (int j{1}, pre{i - 1}; j <= n; ++j) { int tmp{dp[j]}; if (s[i - 1] == t[j - 1]) dp[j] = pre; else dp[j] = min(dp[j - 1], min(dp[j], pre)) + 1; pre = tmp; } } return dp[n]; } }; -
$\bigstar$1092. 最短公共超序列;(难, 需要考虑从后往前遍历, 并且自己构造字符串)
class Solution { public: string shortestCommonSupersequence(string s, string t) { int m = s.size(), n = t.size(); // 存长度 int dp[m + 1][n + 1]; memset(dp, 0, sizeof(dp)); // init for (int j{1}; j <= n; ++j) dp[0][j] = j; for (int i{1}; i <= m; ++i) dp[i][0] = i; // calc for (int i{1}; i <= m; ++i) for (int j{1}; j <= n; ++j) if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1; else dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1; /* str1 = "abac", str2 = "cab" 0 1 2 3 1 2 2 4 2 3 4 3 3 4 4 5 4 4 5 6 */ // for (int i{}; i <= m; ++i) { // for (int j{}; j <= n; ++j) // cout<< dp[i][j]<<"\t"; // cout<<endl; // } // 构造字符串 string ans{}; int i{m}, j{n}; while (i && j) { if (s[i - 1] == t[j - 1]) ans = s[--i] + ans, --j; else if (dp[i][j] == dp[i - 1][j] + 1) ans = s[--i] + ans; else ans = t[--j] + ans; } // 可不计s和t前面的顺序 return t.substr(0, j) + s.substr(0, i) + ans; } }; -
class Solution { public: int countSubstrings(string s, string t) { int m = s.size(), n = t.size(), ans{}; int dpl[m + 1][n + 1], dpr[m + 1][n + 1]; memset(dpl, 0, sizeof(dpl)), memset(dpr, 0, sizeof(dpr)); // 中心扩展, 找相等字符 for (int i{m - 1}; i >= 0; --i) for (int j{n - 1}; j >= 0; --j) dpr[i][j] = s[i] == t[j] ? dpr[i + 1][j + 1] + 1 : 0; for (int i{}; i < m; ++i) for (int j{}; j < n; ++j) if (s[i] == t[j]) dpl[i + 1][j + 1] = s[i] == t[j] ? dpl[i][j] + 1 : 0; else ans += (dpl[i][j] + 1) * (dpr[i + 1][j + 1] + 1); return ans; } };
```cpp
```
子数组(连续的子序列)
-
class Solution { public: int findLength(vector<int> &nums1, vector<int> &nums2) { int n1 = nums1.size(), n2 = nums2.size(); vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1)); int ans{}, i{}, j{}; for (i = 1; i <= n1; ++i) for (j = 1; j <= n2; ++j) { if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1; if (dp[i][j] > ans) ans = dp[i][j]; } return ans; } }; // 滚动数组 class Solution { public: int findLength(vector<int> &nums1, vector<int> &nums2) { int n1 = nums1.size(), n2 = nums2.size(); vector<int> dp(n2 + 1); int ans{}, i{}, j{}; for (i = 1; i <= n1; ++i) for (j = n2; j > 0; --j) { if (nums1[i - 1] == nums2[j - 1]) dp[j] = dp[j - 1] + 1; else dp[j] = 0; if (dp[j] > ans) ans = dp[j]; } return ans; } }; -
class Solution { public: int maxSubArray(vector<int>& nums) { int n = nums.size(); int dp[n]; memset(dp, 0, sizeof(dp)); dp[0] = nums[0]; for (int i{1}; i < n; ++i) dp[i] = max(dp[i - 1] + nums[i], nums[i]); return *max_element(dp, dp + n); } }; // 滚动数组 class Solution { public: int maxSubArray(vector<int>& nums) { int a, b{INT_MIN}, ans{INT_MIN}; for (int num : nums) { a = num + max(b, 0); ans = max(a, ans); b = a; } return ans; } }; -
class Solution { public: int maxProduct(vector<int>& nums) { // 每次记录最大值(正), 最小值(负) int n = nums.size(), mxp[n], mnp[n]; mxp[0] = mnp[0] = nums[0]; for (int i{1}; i < n; ++i) { mnp[i] = min(min(nums[i], mnp[i - 1] * nums[i]), mxp[i - 1] * nums[i]); mxp[i] = max(max(nums[i], mxp[i - 1] * nums[i]), mnp[i - 1] * nums[i]); } return *max_element(mxp, mxp + n); } };滚动数组:
class Solution { public: int maxProduct(vector<int>& nums) { int n = nums.size(), tx{nums[0]}, tn{nums[0]}, mx, mn, ans{nums[0]}; for (int i{1}; i < n; ++i) { mn = min(min(nums[i], tn * nums[i]), tx * nums[i]); mx = max(max(nums[i], tx * nums[i]), tn * nums[i]); tx = mx, tn = mn, ans = max(ans, mx); } return ans; } }; -
1043. 分隔数组以得到最大和; (数组类经典动态规划)
class Solution { public: int maxSumAfterPartitioning(vector<int> &arr, int k) { int n = arr.size(); int dp[n + 1]; memset(dp, 0, sizeof(dp)); for (int i{1}; i <= n; ++i) for (int j{i}, mx{}; i - j < k && j > 0; --j) mx = max(mx, arr[j - 1]), dp[i] = max(dp[i], dp[j - 1] + (i - j + 1) * mx); return dp[n]; } }; -
1186. 删除一次得到子数组最大和 - 力扣（Leetcode）;
-
2606. 找到最大开销的子字符串 - 力扣（Leetcode）;
-
918. 环形子数组的最大和 - 力扣（Leetcode）;
-
2321. 拼接数组的最大分数 - 力扣（Leetcode）;
-
6912. 构造最长非递减子数组 - 力扣（Leetcode）;
class Solution { public: int maxNonDecreasingLength(vector<int>& a, vector<int>& b) { int n = a.size(), ans{1}; vector<vector<int>> dp(n, vector<int>(2, 1)); for (int i{1}; i < n; ++i) { if (a[i - 1] <= a[i]) dp[i][0] = dp[i - 1][0] + 1; if (b[i - 1] <= b[i]) dp[i][1] = dp[i - 1][1] + 1; if (a[i - 1] <= b[i]) dp[i][1] = max(dp[i][1], dp[i - 1][0] + 1); if (b[i - 1] <= a[i]) dp[i][0] = max(dp[i][0], dp[i - 1][1] + 1); ans = max(ans, max(dp[i][0], dp[i][1])); } return ans; } };
多维数组
354. 俄罗斯套娃信封问题 - 力扣（LeetCode）;
1691. 堆叠长方体的最大高度 - 力扣（LeetCode）;
字符串
匹配问题($\bigstar$)
-
class Solution { public: bool isMatch(string s, string p) { int m = s.size(), n = p.size(); bool dp[m + 1][n + 1]; memset(dp, false, sizeof(dp)); dp[0][0] = true; // 初始化第一行 for (int j = 2; j <= n; j++) dp[0][j] = dp[0][j - 2] && p[j - 1] == '*'; // 状态转移 for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (p[j - 1] != '*') dp[i][j] = dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.'); else dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.')); } } return dp[m][n]; } }; -
class Solution { public: bool isMatch(string s, string p) { int m = s.size(), n = p.size(); bool dp[m + 1][n + 1]; memset(dp, false, sizeof(dp)); // 初始化 dp[0][0] = true; // 仅当前面全为*时候才能匹配空字符串 for (int i{1}; i <= n && p[i - 1] == '*'; ++i) dp[0][i] = true; for (int i{1}; i <= m; ++i) { for (int j{1}; j <= n; ++j) { if (s[i - 1] == p[j - 1] || p[j - 1] == '?') dp[i][j] = dp[i - 1][j - 1]; else if (p[j - 1] == '*') // 使用*: (i-1, j), 不使用*: (i, j-1) dp[i][j] = dp[i][j - 1] | dp[i - 1][j]; } } return dp[m][n]; } }; -
32. 最长有效括号; 需要考虑前面的匹配情况.
class Solution { public: int longestValidParentheses(string s) { if (s.empty()) return 0; int ans{}, n = s.size(), dp[n]; // 以s[i]结尾的最长有效括号的长度 memset(dp, 0, sizeof(dp)); for (int i{1}; i < n; ++i) { if (s[i] == '(') continue; // dp[i] = 0; if (s[i - 1] == '(') dp[i] = (i > 1 ? dp[i - 2] : 0) + 2; // s[i]与s[i-1]匹配 // 此时要考虑前面某一字符与s[i-1]组成有效字符串的情况 else if (dp[i - 1] && i - dp[i - 1] && s[i - dp[i - 1] - 1] == '(') dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] > 1 ? dp[i - dp[i - 1] - 2] : 0); ans = max(ans, dp[i]); } return ans; } }; -
-
class Solution { public: int numDecodings(string s) { int n = s.size(), dp[n + 1]; memset(dp, -1, sizeof(dp)); function<int(int)> f = [&](int x) { if (x <= 0) return 1; // found int &res = dp[x]; if (~res) return res; // exists res = 0; if (s[x - 1] != '0') res += f(x - 1); if (x > 1 && s[x - 2] != '0' && stoi(s.substr(x - 2, 2)) <= 26) res += f(x - 2); return res; }; return f(n); } };改成递推:
class Solution { public: int numDecodings(string s) { int n = s.size(), dp[n + 1]; memset(dp, 0, sizeof(dp)); dp[0] = 1; for (int i{1}; i <= n; ++i) { if (s[i - 1] != '0') dp[i] += dp[i - 1]; if (i > 1 && s[i - 2] != '0' && stoi(s.substr(i - 2, 2)) <= 26) dp[i] += dp[i - 2]; } return dp[n]; } }; // class Solution { public: int numDecodings(string s) { int n = s.size(), a{}, b{1}, c{}; for (int i{1}; i <= n; ++i) { a = 0; if (s[i - 1] != '0') a += b; if (i > 1 && s[i - 2] != '0' && stoi(s.substr(i - 2, 2)) <= 26) a += c; c = b, b = a; } return a; } };
回文问题
可以不用DP, 使用双指针或者马拉车都比DP快很多. 但是 dp 作为一种通解还是要掌握的.
-
class Solution { public: int countSubstrings(string s) { int n = s.size(), ans{}; bool dp[n][n]; // s[i:j] 是否为回文 memset(dp, false, sizeof(dp)); for (int i{n - 1}; i >= 0; --i) for (int j{i}; j < n; ++j) if (s[i] == s[j]) if (j - i <= 1) // 单一字符成回文 dp[i][j] = true, ans++; else if (dp[i + 1][j - 1]) // 双字符 dp[i][j] = true, ans++; return ans; } }; -
5. 最长回文子串 - 力扣（LeetCode）;(回文子串那个题的基础上加上更新最大值的操作即可)
class Solution { public: string longestPalindrome(string s) { int n = s.size(), maxL{}, st{}; bool dp[n][n]; memset(dp, false, sizeof(dp)); for (int i{}; i < n; ++i) dp[i][i] = true; for (int i{n - 1}; i >= 0; --i) for (int j{i}; j < n; ++j) { if (s[i] == s[j]) if (j - i <= 1) dp[i][j] = true; else if (dp[i + 1][j - 1]) dp[i][j] = dp[i + 1][j - 1]; // 更新 if (dp[i][j] && j - i + 1 > maxL) maxL = j - i + 1, st = i; } return s.substr(st, maxL); } }; -
class Solution { public: int longestPalindromeSubseq(string s) { int n = s.size(); int dp[n][n]; memset(dp, 0, sizeof(dp)); for (int i{n - 1}; i >= 0; --i) dp[i][i] = 1; for (int i{n - 1}; 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 + 1][j], dp[i][j - 1]); return dp[0][n - 1]; } }; // 滚动数组优化 class Solution { public: int longestPalindromeSubseq(string s) { int n = s.size(); int dp[n]; memset(dp, 0, sizeof(dp)); for (int i{}; i < n; ++i) dp[i] = 1; for (int i{n - 1}; i >= 0; --i) for (int j{i + 1}, pre{}; j < n; ++j) { int tmp{dp[j]}; dp[j] = (s[i] == s[j]) ? pre + 2 : max(dp[j - 1], dp[j]); pre = tmp; } return dp[n - 1]; } }; -
131. 分割回文串;(用动态规划预处理回文子串)
class Solution { public: vector<vector<string>> partition(string s) { int n = s.size(); bool g[n][n]; // s[i:j] is Palindrome memset(g, 0, sizeof(g)); for (int i{n - 1}; i >= 0; --i) for (int j{i}; j < n; ++j) g[i][j] = (s[i] == s[j] && (j - i <= 1 || g[i + 1][j - 1])); vector<string> path; vector<vector<string>> ans; function<void(int)> f = [&](int x) { // x: start index if (x == n) { ans.emplace_back(path); return; } for (int i{}; i < n; ++i) { if (!g[x][i]) continue; path.emplace_back(s.substr(x, i - x + 1)); f(i + 1); path.pop_back(); } }; f(0); return ans; } }; -
132. 分割回文串 II;(用到了上面预处理的方法)
class Solution { public: int minCut(string s) { int n = s.size(), dp[n]; bool g[n][n]; memset(g, 0, sizeof(g)); for (int i{n - 1}; i >= 0; --i) for (int j{i}; j < n; ++j) g[i][j] = (s[i] == s[j] && (j - i <= 1 || g[i + 1][j - 1])); memset(dp, 0x3f, sizeof(dp)); // max cut for (int r{}; r < n; ++r) { if (g[0][r]) dp[r] = 0; else { for (int l{}; l < r; ++l) if (g[l + 1][r]) dp[r] = min(dp[r], dp[l] + 1); } } return dp[n - 1]; } };单调性问题
926. 将字符串翻转到单调递增;剑指 Offer II 092. 翻转字符;
树形 dp
换根 dp
状态压缩 dp
主要处理子集问题..