9-动态规划
动态规划步骤
动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。
所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。
动态规划的解题步骤（动规五部曲）
确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组
1.基础题目
509. 斐波那契数
//509. 斐波那契数
//递归
class Solution {
public:
int fib(int n) {
if(n == 0 || n == 1) return n;
return fib(n - 1) + fib(n - 2);
}
};
//动态规划
class Solution {
public:
int fib(int n) {
int dp[31] = {0};
dp[0] = 0;
dp[1] = 1;
for(int i = 2; i <= n ;i++)
{
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
};
70. 爬楼梯
//70. 爬楼梯
class Solution {
public:
int climbStairs(int n) {
int dp[46] = {0};
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= n ;i++)
{
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
};
746. 使用最小花费爬楼梯
//746. 使用最小花费爬楼梯
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
vector<int> res(cost.size()+1,0);
if (cost.size() == 1) return cost[0];
if (cost.size() == 2) return min(cost[0],cost[1]);
for (int i = 2; i <= cost.size(); ++i) {
res[i] =min(res[i-1] + cost[i-1],res[i-2]+ cost[i-2]);
}
return res[cost.size()];
}
};
62. 不同路径
//62. 不同路径
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> res(m,vector<int>(n,1));
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
res[i][j] = res[i][j-1] + res[i-1][j];
}
}
return res[m-1][n-1];
}
};
63. 不同路径 II
//63. 不同路径 II
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
if (obstacleGrid.back().back() == 1) return 0;
//改变标识
for (int i = 0; i < obstacleGrid.size(); ++i) {
for (int j = 0; j < obstacleGrid[0].size(); ++j) {
if (obstacleGrid[i][j]) obstacleGrid[i][j] = -1;
}
}
//第一层
int flag = 1;
for (int i = 0; i < obstacleGrid.size(); ++i) {
if (obstacleGrid[i][0] == -1) flag=0;
else obstacleGrid[i][0] = flag;
}
flag = 1;
for (int i = 0; i < obstacleGrid[0].size(); ++i) {
if (obstacleGrid[0][i] == -1) flag=0;
else obstacleGrid[0][i] = flag;
}
int m = obstacleGrid.size(),n =obstacleGrid[0].size();
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
if (obstacleGrid[i][j] == -1) continue;
else if (obstacleGrid[i-1][j] == -1 && obstacleGrid[i][j-1] == -1) obstacleGrid[i][j] = 0;
else if (obstacleGrid[i][j-1] == -1) obstacleGrid[i][j] = obstacleGrid[i-1][j];
else if (obstacleGrid[i-1][j] == -1) obstacleGrid[i][j] = obstacleGrid[i][j-1];
else if (obstacleGrid[i-1][j] != -1 && obstacleGrid[i][j-1] != -1)
obstacleGrid[i][j] = obstacleGrid[i][j-1] + obstacleGrid[i-1][j];
}
return obstacleGrid[m-1][n-1];
}
};
343. 整数拆分
从1遍历j，然后有两种渠道得到dp[i].
一个是j * (i - j) 直接相乘。
一个是j * dp[i - j]，相当于是拆分(i - j)
//343. 整数拆分
class Solution {
public:
int num[59];
int integerBreak(int n) {
num[2] = 1;
for (int i = 3; i <= n; ++i) {
for (int j = 1; j <= i /2; ++j) {
num[i] = max(max(num[i],j*(i-j)),j*num[i-j]);
}
}
return num[n];
}
};
96. 不同的二叉搜索树
class Solution {
public:
int numTrees(int n) {
int dp[20]={1};
dp[1] = 1;
//递推公式dp[i] += dp[i-j] * dp[j]
for (int i = 2; i <=n ; ++i) {
for (int j = 0; j < i ; ++j) {
dp[i] += dp[j] * dp[i- j - 1] ;
}
}
return dp[n];
}
};
64. 最小路径和
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
for (int i = 1; i < grid.size(); ++i) grid[i][0] +=grid[i - 1][0];
for (int i = 1; i < grid[0].size(); ++i) grid[0][i] +=grid[0][i - 1];
for (int i = 1; i < grid.size(); ++i) {
for (int j = 1; j < grid[0].size(); ++j) {
grid[i][j] += min(grid[i-1][j],grid[i][j-1]);
}
}
return grid.back().back();
}
};
542. 01 矩阵
class Solution {
int findmin(vector<vector<int>>&dp, int i, int j)
{
int mins = dp[i][j];
if(i > 0) mins = min(mins,dp[i - 1][j]+1);
if(j > 0) mins = min(mins,dp[i][j - 1]+1);
if(i < dp.size() - 1) mins = min(mins,dp[i + 1][j]+1);
if(j < dp[0].size() - 1) mins = min(mins,dp[i][j + 1]+1);
return mins;
}
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
//初始化
vector<vector<int>> dp(mat);
for (int i = 0; i < mat.size(); i++)
for (int j = 0; j < mat[0].size(); j++)
if(mat[i][j] == 1) dp[i][j] = INT32_MAX / 2;
//上边遍历
for (int i = 0; i < mat.size(); i++)
for (int j = 0; j < mat[0].size(); j++)
dp[i][j] = findmin(dp,i,j);
//下表遍历
for (int i = mat.size() - 1; i >= 0; i--)
for (int j =mat[i].size() - 1; j >= 0; j--)
dp[i][j] = findmin(dp,i,j);
return dp;
}
};
221. 最大正方形*
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int maxs = 0;
vector<vector<int>> dp(matrix.size()+1,vector<int>(matrix[0].size()+1,0));
for (int i = 1; i <= matrix.size(); ++i) {
for (int j = 1; j <= matrix[0].size(); ++j) {
if (matrix[i-1][j-1]=='1')dp[i][j] = min(dp[i-1][j-1],min(dp[i][j-1],dp[i-1][j]))+1;
maxs = max(maxs,dp[i][j]);
}
}
return maxs * maxs;
}
};
剑指 Offer 46. 把数字翻译成字符串
class Solution {
public:
int translateNum(int num) {
string s = to_string(num);
vector<int> dp(s.size() + 1);
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= s.size();i++)
{
if(s[i - 2] == '1' || (s[i - 2] == '2') && (s[i - 1] < '6')) dp[i] = dp[i - 1] + dp[i - 2];
else dp[i] = dp[i - 1];
}
return dp.back();
}
};
91. 解码方法
class Solution {
public:
int numDecodings(string s) {
if(s[0] == '0') return 0;
//dp[i] -> s[i - 1]的解码数量
int dp[101] = {0};
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= s.size() ;i++)
{
if(s[i - 1] == '0' && (s[i - 2] > '2' || s[i - 2] == '0')) return 0;
if(s[i - 1] == '0') dp[i] = dp[i - 2];
else if(s[i - 2] == '1' || s[i - 2] == '2' && s[i - 1] <= '6') dp[i] = dp[i - 1] + dp[i - 2];
else dp[i] = dp[i - 1];
}
return dp[s.size()];
}
};
650. 只有两个键的键盘
//方法一动态规划
class Solution {
public:
int minSteps(int n) {
vector<int> dp(n + 1,0);
for (int i = 2; i <=n; ++i) {
dp[i] = i;
for (int j = 2; j <= (int)sqrt(n); ++j) {
if (i % j == 0)
{
dp[i] = dp[j] + dp[i / j];
break;
}
}
}
return dp[n];
}
};
//方法二 求最大公因数和
class Solution {
public:
int minSteps(int n) {
if(n == 1) return 0;
if(n == 2) return 2;
for(int i = 2; i <= sqrt(n); i++)
{
if(n % i == 0) return minSteps(n / i) + minSteps(i);
}
return n;
}
};
152. 乘积最大子数组
class Solution {
public:
int maxProduct(vector<int>& nums) {
int mins = 1 , maxs = 1, ans = INT_MIN;
for(int x : nums)
{
if(x < 0) swap(mins,maxs);
mins = min(x, x * mins);
maxs = max(x, x * maxs);
ans = max(ans,maxs);
}
return ans;
}
};
剑指 Offer 49. 丑数
class Solution {
public:
int nthUglyNumber(int n) {
vector<int> dp(n);
dp[0] = 1;
int r1 = 0,r2 = 0,r3 = 0;
for(int i = 1; i < n; i++)
{
int m1 = dp[r1] * 2,m2 = dp[r2] * 3,m3 = dp[r3] * 5;
dp[i] = min({m1,m2,m3});
if(dp[i] == m1) r1++;
if(dp[i] == m2) r2++;
if(dp[i] == m3) r3++;
}
return dp.back();
}
};
剑指 Offer 47. 礼物的最大价值
class Solution {
public:
int maxValue(vector<vector<int>>& grid) {
int max_V = 0;
for(int i = 1; i < grid.size();i++) grid[i][0] += grid[i - 1][0];
for(int i = 1; i < grid[0].size();i++) grid[0][i] += grid[0][i - 1];
for(int i = 1; i < grid.size();i++)
{
for(int j = 1; j < grid[0].size();j++)
{
grid[i][j] = max(grid[i - 1][j],grid[i][j - 1]) + grid[i][j];
}
}
return grid.back().back();
}
};
LCR 091. 粉刷房子
class Solution {
public:
int minCost(vector<vector<int>>& costs) {
for(int i = 1;i < costs.size();i++)
{
costs[i][0] += min(costs[i - 1][1],costs[i - 1][2]);
costs[i][1] += min(costs[i - 1][0],costs[i - 1][2]);
costs[i][2] += min(costs[i - 1][0],costs[i - 1][1]);
}
return min({costs.back()[0],costs.back()[1],costs.back()[2]});
}
};
LCR 092. 将字符串翻转到单调递增
class Solution {
public:
int minFlipsMonoIncr(string s) {
vector<vector<int>> dp(s.size(),vector<int>(2,0));
dp[0][0] = (s[0] == '1');
dp[0][1] = (s[0] == '0');
for(int i = 1 ; i < s.size() ;i++)
{
dp[i][0] += (s[i] == '1') + dp[i - 1][0];
dp[i][1] += min(dp[i - 1][0] , dp[i - 1][1]) + (s[i] == '0');
}
return min(dp.back()[0],dp.back()[1]);
}
};
LCR 096. 交错字符串
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
if(s1.size() + s2.size() != s3.size()) return false;
//dp[i][j] 是否能组成 s[i + j] 的字符串
vector<vector<bool>> dp(s1.size() + 1,vector<bool>(s2.size() + 1,false));
//初始化 i = 0 或 j = 0
dp[0][0] = true;
for(int i = 1 ; i <= s2.size();i++) dp[0][i] = dp[0][i - 1] && s2[i - 1] == s3[i - 1];
for(int i = 1 ; i <= s1.size();i++) dp[i][0] = dp[i - 1][0] && s1[i - 1] == s3[i - 1];
for(int i = 1; i <= s1.size();i++)
{
for(int j = 1; j <= s2.size();j++)
{
dp[i][j] = (dp[i][j - 1] && s2[j - 1] == s3[i + j - 1]) || (dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]);
}
}
return dp.back().back();
}
};
LCR 100. 三角形最小路径和
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int res = INT_MAX;
for(int i = 1; i < triangle.size();i++)
{
triangle[i][0] += triangle[i - 1][0];
triangle[i].back() += triangle[i - 1].back();
}
for(int i = 1; i < triangle.size() ;i++)
{
for(int j = 1;j < i ;j++)
{
triangle[i][j] += min(triangle[i - 1][j - 1],triangle[i - 1][j]);
}
}
for(int i = 0; i < triangle.back().size();i++) res = min(res,triangle.back()[i]);
return res;
}
};
面试题 08.01. 三步问题
class Solution {
public:
int waysToStep(int n) {
if(n == 1) return 1;
if(n == 2) return 2;
if(n == 3) return 4;
long arr[3] = {1,2,4} , MAXS = 1000000007;
for(int i = 4; i <= n ;i++)
{
int p = (arr[0] + arr[1] + arr[2]) % MAXS;
arr[0] = arr[1];
arr[1] = arr[2];
arr[2] = p;
}
return arr[2];
}
};
面试题 08.06. 汉诺塔问题
// 递归经典问题
class Solution {
public:
void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
int n = A.size();
move(n, A, B, C);
}
// 自定义函数
void move(int n, vector<int>& A, vector<int>& B, vector<int>& C)
{
if (n == 1)
{
C.push_back(A.back());
A.pop_back(); // 删除最后一个元素
return;
}
move(n - 1, A, C, B); // 移动n-1个盘子从A移动到B
C.push_back(A.back()); // 移动第n个盘子从A到C
A.pop_back(); // 没有这句会WA
move(n- 1, B, A, C); // 移动n-1个盘子从B移动到C
}
};
面试题 08.13. 堆箱子
class Solution {
bool ismanzu(const vector<int> &a, const vector<int> &b)
{
return a[0] < b[0] && a[1] < b[1] && a[2] < b[2];
}
public:
int pileBox(vector<vector<int>>& box) {
sort(box.begin(),box.end(),[&](const vector<int> &a, const vector<int> &b){
if(a[2] == b[2] && a[1] == b[1]) return a[0] < b[0];
if(a[2] == b[2]) return a[1] < b[1];
return a[2] < b[2];
});
vector<int> dp(box.size(),0);
int res = box[0][2];
dp[0] = box[0][2];
for(int i = 1; i < box.size();i++)
{
dp[i] = box[i][2];
for(int j = 0; j < i ; j++)
{
if(ismanzu(box[j],box[i])) dp[i] = max(dp[i],box[i][2] + dp[j]);
}
//cout << dp[i] << " ";
res = max(res, dp[i]);
}
return res;
}
};
面试题 08.14. 布尔运算
class Solution {
public:
int countEval(string s, int result) {
// 1, 2, 3
// 1->2->3, 3->2->1
// 1^1, 2^2, 3^3;
if (s.empty()) return 0;
if (s.size() == 1) return s[0] - '0' == result;
int n = s.size(), m = n / 2;
int f[m][m][2];
memset(f, 0, sizeof f);
for (int len = 1; len <= m; len ++)
for (int i = 0; i + len - 1 < m; i ++) {
int j = i + len - 1;
if (len == 1) {
int t = i * 2;
f[i][j][get(s[t + 1], s[t] - '0', s[t + 2] - '0')] = 1;
} else {
for (int k = i; k <= j; k ++) { // 一定要保证状态划分的边界线正确
int t = k * 2;
if (k == i) {
if (f[k + 1][j][0]) f[i][j][get(s[t + 1], s[t] - '0', 0)] += f[k + 1][j][0];
if (f[k + 1][j][1]) f[i][j][get(s[t + 1], s[t] - '0', 1)] += f[k + 1][j][1];
} else if (k == j) {
if (f[i][k - 1][0]) f[i][j][get(s[t + 1], s[t + 2] - '0', 0)] += f[i][k - 1][0];
if (f[i][k - 1][1]) f[i][j][get(s[t + 1], s[t + 2] - '0', 1)] += f[i][k - 1][1];
} else {
if (f[i][k - 1][0] && f[k + 1][j][0]) f[i][j][get(s[t + 1], 0, 0)] += f[i][k - 1][0] * f[k + 1][j][0];
if (f[i][k - 1][0] && f[k + 1][j][1]) f[i][j][get(s[t + 1], 0, 1)] += f[i][k - 1][0] * f[k + 1][j][1];
if (f[i][k - 1][1] && f[k + 1][j][0]) f[i][j][get(s[t + 1], 1, 0)] += f[i][k - 1][1] * f[k + 1][j][0];
if (f[i][k - 1][1] && f[k + 1][j][1]) f[i][j][get(s[t + 1], 1, 1)] += f[i][k - 1][1] * f[k + 1][j][1];
}
// cout << k << ',' << f[i][j][0] << ',' << f[i][j][1] << endl;
}
// if (i == 2 && j == 3) exit(0);
}
}
return f[0][m - 1][result];
}
bool get(char op, int t1, int t2) {
if (op == '^') return t1 ^ t2;
if (op == '|') return t1 | t2;
return t1 & t2;
}
};
1235. 规划兼职工作***
class Solution {
public:
int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
int n = startTime.size();
array<int, 3> jobs[n];
for (int i = 0; i < n; ++i)
jobs[i] = {endTime[i], startTime[i], profit[i]};
sort(jobs, jobs + n, [](auto &a, auto &b) { return a[0] < b[0]; }); // 按照结束时间排序
int f[n + 1];
f[0] = 0;
for (int i = 0; i < n; ++i) {
int j = upper_bound(jobs, jobs + i, array<int, 3>{jobs[i][1], INT_MAX}) - jobs;
f[i + 1] = max(f[i], f[j] + jobs[i][2]);
}
return f[n];
}
};
2830. 销售利润最大化*
与上题类似
class Solution {
public:
int maximizeTheProfit(int n, vector<vector<int>>& offers) {
sort(offers.begin(),offers.end(),[](const vector<int> &a,const vector<int> &b){
return a[1] < b[1];
});
int dp[offers.size() + 1];
dp[0] = 0;
for(int i = 0; i < offers.size();i++)
{
int j = lower_bound(offers.begin(),offers.begin() + i,offers[i][0],[](const vector<int> a , int b){
return a[1] < b;
}) - offers.begin();
dp[i + 1] = max(dp[i],offers[i][2] + dp[j]);
}
return dp[offers.size()];
}
};
486. 预测赢家
class Solution {
/*
零和博弈dp【L】【R】 代表L - R中能取到最大的
计算能取到最大的为 所有值 - 对方能取到最小的
*/
public:
bool predictTheWinner(vector<int>& nums) {
int dp[20][20];
memset(dp,-1,sizeof(dp));
function<int(int,int)> dfs= [&](int L , int R){
if(dp[L][R] != -1) return dp[L][R];
if(L == R) return dp[L][R] = nums[L];
return dp[L][R] = accumulate(nums.begin() + L,nums.begin() + R + 1, 0) - min(dfs(L + 1, R),dfs(L , R - 1));
};
return dfs(0,nums.size() - 1) * 2 >= accumulate(nums.begin() ,nums.end() , 0);
}
};
887. 鸡蛋掉落
class Solution {
public:
/*
有 K 个蛋，扔 T 次，求可以确定 F 的个数，然后得出 N 个楼层
dp[i][j]代表当有i次操作，且有j个鸡蛋时能测出的楼层数，再来考虑状态转移方程如何写，比如先在中间楼层扔个鸡蛋：
鸡蛋碎掉：剩下j-1个鸡蛋和i-1次操作，dp[i-1][j-1]
鸡蛋没碎：剩下j个鸡蛋和i-1次操作，dp[i-1][j]
那么加上当前层，总共可以通过i次操作和j个鸡蛋查找的层数范围是 [0, dp[i-1][j-1] + dp[i-1][j] + 1]，然后只要判断dp[i][j]大于楼层N的话，就可以返回次数i了。这样就可以得到状态转移方程如下：
*/
int superEggDrop(int K, int N) {
vector<vector<int>> dp(N + 1, vector<int>(K + 1));
int m = 0;
while (dp[m][K] < N) {
++m;
for (int j = 1; j <= K; ++j) {
dp[m][j] = dp[m - 1][j - 1] + dp[m - 1][j] + 1;
}
}
return m;
}
};
/*
优化
class Solution {
public:
int superEggDrop(int K, int N) {
vector<int> dp(K + 1);
int res = 0;
for (; dp[K] < N; ++res) {
for (int i = K; i > 0; --i) {
dp[i] = dp[i] + dp[i - 1] + 1;
}
}
return res;
}
};
*/
717. 1 比特与 2 比特字符
class Solution {
public:
bool isOneBitCharacter(vector<int>& bits) {
if(bits.back() == 1) return false;
bits.pop_back();
vector<bool> dp(bits.size() + 1);
dp[0] = true;
for(int i = 1; i <= bits.size();i++)
{
if(bits[i - 1] == 0) dp[i] = dp[i - 1] || (i >= 2 && bits[i - 2] == 1 && dp[i - 2]);
else dp[i] = (i >= 2 && bits[i - 2] == 1 && dp[i - 2]);
}
return dp.back();
}
};
931. 下降路径最小和
class Solution {
public:
int minFallingPathSum(vector<vector<int>>& matrix) {
for(int i = 1; i < matrix.size();i++)
{
for(int j = 0; j < matrix[0].size();j++)
{
if(j == 0) matrix[i][j] += min(matrix[i - 1][j],matrix[i - 1][j + 1]);
else if(j == matrix[0].size() - 1) matrix[i][j] += min(matrix[i - 1][j],matrix[i - 1][j - 1]);
else matrix[i][j] += min({matrix[i - 1][j],matrix[i - 1][j + 1],matrix[i - 1][j - 1]});
}
}
//for(int i = 0; i < matrix[0].size();i++) cout << matrix.back()[i]<< " ";
for(int i = 1; i < matrix[0].size();i++) matrix.back()[i] = min(matrix.back()[i],matrix.back()[i - 1]);
return matrix.back().back();
}
};
312. 戳气球
//用楼主的思路写的C++版本，楼主的状态转移方程真的赞！！
class Solution {
public:
int maxCoins(vector<int>& nums) {
//可以先将题目中要求的nums[-1] = 1，nums[n] = 1，添加到数组
int n = nums.size() + 2;
nums.insert(nums.begin(), 1);
nums.push_back(1);
//共有气球n个，定义dp[0][n - 1]为（0，n - 1）区间内能够得到的最大值，
//此处0和n-1均取不到，第0个气球和第n-1个气球都是添加的方便计算
//dp[0][n - 1]为最后要求的答案，假设最后戳破的气球为第i个，状态转移方程：
//dp[start][end] = dp[start][i] + dp[i][end] + nums[start] * nums[i] * nums[end] (start < i < end)
//从状态转移方程看出，每次需要后面遍历的结果，即dp[start][i]和dp[i][end]，不需要管start前面的值
vector<vector<int>> dp(n, vector<int>(n, 0));
for(int start = n - 1; start >= 0; --start){
for(int end = start; end < n ; ++end){
//对于（start，end）区间气球不够一个的就不用戳了，
//计算最后戳破（start，end）区间下标为i的气球
for(int i = start + 1; i < end; ++i){
dp[start][end] = max(dp[start][end], dp[start][i] + dp[i][end] + nums[start] * nums[i] * nums[end]);
}
}
}
return dp[0][n - 1];
}
};
1024. 视频拼接
class Solution {
public:
int videoStitching(vector<vector<int>>& clips, int time) {
//令 dp[i]表示将区间 [0,i) 覆盖所需的最少子区间的数量
vector<int> dp(time + 1, INT_MAX - 1);
dp[0] = 0;
for (int i = 1; i <= time; i++) {
for (auto& it : clips) {
if (it[0] < i && i <= it[1]) {
dp[i] = min(dp[i], dp[it[0]] + 1);
}
}
}
return dp[time] == INT_MAX - 1 ? -1 : dp[time];
}
};
712. 两个字符串的最小ASCII删除和
class Solution {
public:
int minimumDeleteSum(string s1, string s2) {
vector<vector<int>> dp(s1.size() + 1,vector<int>(s2.size() + 1));
for(int i = 1; i <= s1.size();i++) dp[i][0] += dp[i - 1][0] + s1[i - 1];
for(int i = 1; i <= s2.size();i++) dp[0][i] += dp[0][i - 1] + s2[i - 1];
for(int i = 1; i <= s1.size(); i++)
{
for(int j = 1; j <= s2.size();j++)
{
if(s1[i - 1] == s2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
else dp[i][j] = min(dp[i - 1][j] + s1[i - 1], dp[i][j - 1] + s2[j - 1]);
}
}
return dp.back().back();
}
};
446. 等差数列划分 II - 子序列（NO）
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums) {
int res = 0;
int n = nums.size();
// dp[3][2] = 5 -> nums[3]结尾 公差为2 的 等差数列（长度大于2）的个数为 5
vector<unordered_map<long long, int>> dp(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
long long d = (long long) nums[i] - nums[j];
dp[i][d] += dp[j][d] + 1;
// dp[j][d] 联合上 dp[i] 表示了长度至少为3的等差数列
res += dp[j][d];
}
}
return res;
}
};
354. 俄罗斯套娃信封问题
class Solution {
public:
//即求解最长递增子序列（LIS）的长度,把二维降到一维
int maxEnvelopes(vector<vector<int>>& envelopes) {
//首先，对信封数组按照宽度升序，高度降序的顺序进行排序。这样做的目的是为了保证在宽度相同的情况下，只有最高的信封可以被选中，避免出现宽度相同的信封互相套娃的情况。
sort(envelopes.begin(), envelopes.end(), [](const vector<int> &a, const vector<int> &b){
return a[0] == b[0] ? a[1] > b[1]: a[0] < b[0];
});
//然后，创建一个空的动态数组 dp，用来存储长度为 i+1 的 LIS 中最小的末尾元素的值。初始时，dp 为空。
vector<int> dp; //长度为 i+1 的地方 最小的数字
//接着，遍历排序后的信封数组，对于每个信封 e，使用二分查找在 dp 中找到第一个大于等于 e[1] 的位置 p，如果 p 不存在，说明 e[1] 大于 dp 中的所有元素，那么就将 e[1] 添加到 dp 的末尾，表示找到了一个更长的 LIS；如果 p 存在，说明 e[1] 可以替换 dp 中的某个元素，使得 LIS 的末尾元素更小，那么就将 dp[p] 更新为 e[1]，表示找到了一个更优的 LIS。
for(const auto &e: envelopes) {
auto p = lower_bound(dp.begin(), dp.end(), e[1]); //二分查找第一个大于等于的地方
if(p == dp.end()) dp.push_back(e[1]);
else *p = e[1];
}
return dp.size();
}
};
2.背包问题
1.0-1背包
问题描述：有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
在下面的讲解中，我举一个例子：
背包最大重量为4。
物品为：
| 重量 | 价值 | |
|---|---|---|
| 物品0 | 1 | 15 |
| 物品1 | 3 | 20 |
| 物品2 | 4 | 30 |
一维dp数组（滚动数组）
动规五部曲分析如下：
1.确定dp数组的定义
在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。
2.一维dp数组的递推公式
dp[j]为 容量为j的背包所背的最大价值，dp[j]可以通过dp[j - weight[i]]推导出来，dp[j - weight[i]]表示容量为j - weight[i]的背包所背的最大价值。
dp[j - weight[i]] + value[i] 表示 容量为 j - 物品i重量 的背包 加上 物品i的价值。（也就是容量为j的背包，放入物品i了之后的价值即：dp[j]）
此时dp[j]有两个选择，一个是取自己dp[j] 相当于 二维dp数组中的
dp[i-1][j]
，即不放物品i，一个是取dp[j - weight[i]] + value[i]，即放物品i，指定是取最大的，毕竟是求最大价值，
所以递归公式为：
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
3.一维dp数组初始化
dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。
那么我假设物品价值都是大于0的，所以dp数组初始化的时候，都初始为0就可以了。
4.一维dp数组遍历顺序(先物品，再背包，背包倒序)
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
倒序遍历是为了保证物品i只被放入一次！。但如果一旦正序遍历了，那么物品0就会被重复加入多次！
举一个例子：物品0的重量weight[0] = 1，价值value[0] = 15
完整代码：
void test_1_wei_bag_problem() {
vector<int> weight = {1, 3, 4};
vector<int> value = {15, 20, 30};
int bagWeight = 4;
// 初始化
vector<int> dp(bagWeight + 1, 0);
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
cout << dp[bagWeight] << endl;
}
int main() {
test_1_wei_bag_problem();
}
416. 分割等和子集
题解：分为等和子集，可以理解为把集合划分为两份。让两份和相等。那么和的二分之一为背包容量，nums为物品，物品的价值等于物品的重量，求价值最大化。就是一个01背包问题，求最大背包能不能填满，即填满后等不等于nums的二分之一。
//416. 分割等和子集
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(),nums.end(),0);
if (sum % 2 == 1) return false;
else sum/=2;
vector<int>dp(sum+1,0);
for (int i = 0; i < nums.size(); ++i) {
for (int j = sum; j >=nums[i] ; --j) {
dp[j] = max(dp[j],dp[j - nums[i]]+nums[i]);
}
}
return dp.back() == sum;
}
};
1049. 最后一块石头的重量 II
那么分成两堆石头，一堆石头的总重量是dp[target]，另一堆就是sum - dp[target]。
在计算target的时候，target = sum / 2 因为是向下取整，所以sum - dp[target] 一定是大于等于dp[target]的。
那么相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target]。
//1049. 最后一块石头的重量 II
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int sum = accumulate(stones.begin(),stones.end(),0) / 2;
vector<int> dp(sum+1,0);
for (int i = 0; i < stones.size(); ++i) {
for (int j = sum; j >= stones[i]; --j) {
dp[j] = max(dp[j],dp[j-stones[i]]+stones[i]);
}
}
return accumulate(stones.begin(),stones.end(),0) - 2 * dp.back();
}
};
494. 目标和
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sum = accumulate(nums.begin(),nums.end(),0);
if((sum + target) % 2 == 1 || (sum + target) < 0) return 0;
int add = (sum + target) / 2;
vector<int> dp(add+1,0);
dp[0] = 1;
for (int i = 0; i < nums.size(); ++i) {
for (int j = add; j >= nums[i]; --j) {
dp[j] += dp[j-nums[i]];
}
}
return dp.back();
}
};
474. 一和零
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
//dp[i][j]为 i 个0 ，j个0时候，能最多的子集
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
//dp[i][j] = max(dp[i][j],dp[i - ze][j-one] + 1);
for (int i = 0; i < strs.size(); ++i) {
int ze = std::count(strs[i].begin(), strs[i].end(),'0');
int one = strs[i].size() - ze;
for (int j = m; j >= ze; --j) {
for (int k = n; k >= one; --k) {
dp[j][k] = max( dp[j][k],dp[j - ze][k-one] + 1);
}
}
}
return dp[m][n];
}
};
2.完全背包问题
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。
背包最大重量为4。
物品为：
| 重量 | 价值 | |
|---|---|---|
| 物品0 | 1 | 15 |
| 物品1 | 3 | 20 |
| 物品2 | 4 | 30 |
每件商品都有无限个！
问背包能背的物品最大价值是多少？
首先在回顾一下01背包的核心代码
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
我们知道01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。
而完全背包的物品是可以添加多次的，所以要从小到大去遍历，即：
// 先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
518. 零钱兑换 II（组合）
//518. 零钱兑换 II
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int> dp(amount+1,0);
dp[0] = 1;
for (int i = 0; i < coins.size(); ++i) {
for (int j = coins[i]; j <= amount; ++j) {
dp[j]+=dp[j-coins[i]];
}
}
return dp[amount];
}
};
377. 组合总和 Ⅳ（排列）
//377. 组合总和 Ⅳ
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target+1,0);
dp[0] = 1;
for (int i = 0; i <= target ; ++i)
{
for (int j = 0; j < nums.size(); ++j){
if (i-nums[j]>=0 && dp[i] < INT_MAX - dp[i-nums[j]])
dp[i]+=dp[i-nums[j]];
}
}
return dp[target];
}
};
322. 零钱兑换
//322. 零钱兑换
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount+1,INT_MAX);
dp[0] = 0;
for (int i = 0; i < coins.size(); ++i) {
for (int j = coins[i]; j <= amount ; ++j) {
if (dp[j-coins[i]]!=INT_MAX)
{
dp[j] = min(dp[j],dp[j-coins[i]]+1);
}
}
}
if(dp[amount]==INT_MAX) return -1;
return dp[amount];
}
};
279. 完全平方数
//279. 完全平方数
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n+1,INT_MAX);
dp[0] = 0;
for (int i = 0; i <= n; ++i) {
for (int j = 1; j*j <= i ; ++j) {
dp[i] = min(dp[i-j*j]+1,dp[i]);
}
}
return dp[n];
}
};
139. 单词拆分
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
vector<bool> dp(s.size()+1, false);
dp[0] = true;
for (int i = 1; i <= s.size(); ++i) {
for (int j = 0; j < wordDict.size(); ++j) {
if (i >= wordDict[j].size() && dp[i - wordDict[j].size()] && wordDict[j] == s.substr(i-wordDict[j].size(),wordDict[j].size()))
{
dp[i] = true;
}
}
}
return dp.back();
}
};
1155. 掷骰子等于目标和的方法数
class Solution {
public:
int numRollsToTarget(int n, int k, int target) {
//背包问题的动态规划
//1155. 掷骰子等于目标和的方法数
if(target < n || target > n * k) return 0;
if(n == 1) return 1;
const int M = 1e9 + 7;
vector<vector<int>> dp(n + 1, vector<int>(target + 1));
dp[0][0] = 1;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= target; j++)
{
for (int m = 1; m <= k; m++)
{
if(j >= m) dp[i][j]= (long)(dp[i][j] + dp[i - 1][j - m]) % M;
}
}
}
return dp.back().back();
}
};
剑指 Offer 60. n个骰子的点数
class Solution {
public:
vector<double> dicesProbability(int n) {
//dp[i][j] 表示i个骰子 投出j的次数（背包问题）
vector<vector<int>> dp(n + 1,vector<int>(n * 6 + 1,0));
for(int i = 1;i <= 6;i++) dp[1][i] = 1;
for(int i = 2;i <= n;i++)
{
for(int j = i; j <= i * 6;j++)
{
for(int k = 1; k <= 6 && j - k >= 0; k++)
{
if(dp[i - 1][j - k] != 0)
dp[i][j] += dp[i - 1][j - k];
}
}
}
int sum = accumulate(dp.back().begin(),dp.back().end(),0);
vector<double> res;
for(int j = n; j <= n * 6;j++)
{
res.push_back((double)dp.back()[j] / sum);
}
return res;
}
};
53. 最大子数组和
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int cur = 0 , MAX = nums[0];
for(int x : nums)
{
cur = max(cur + x , x);
MAX = max(MAX,cur);
}
return MAX;
}
};
918. 环形子数组的最大和
https://leetcode.cn/problems/maximum-sum-circular-subarray/
class Solution {
public:
//total为数组的总和，maxSum为最大子数组和，minSum为最小子数组和，curMax为包含当前元素的最大子数组和，curMin为包含当前元素的最小子数组和
int maxSubarraySumCircular(vector<int>& A) {
int total = 0, maxSum = A[0], curMax = 0, minSum = A[0], curMin = 0;
for (int& a : A) {
curMax = max(curMax + a, a);
maxSum = max(maxSum, curMax);
curMin = min(curMin + a, a);
minSum = min(minSum, curMin);
total += a;
}
return maxSum > 0 ? max(maxSum, total - minSum) : maxSum;
}
};
3.总结
背包递推公式
问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); ，对应题目如下：
问装满背包有几种方法：dp[j] += dp[j - nums[i]] ，对应题目如下：
- 动态规划：494.目标和(opens new window)
- 动态规划：518. 零钱兑换 II(opens new window)
- 动态规划：377.组合总和Ⅳ(opens new window)
- 动态规划：70. 爬楼梯进阶版（完全背包）(opens new window)
问背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); ，对应题目如下：
问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j]); ，对应题目如下：
遍历顺序
01背包
一维dp数组01背包只能先遍历物品再遍历背包容量，且第二层for循环是从大到小遍历。
一维dp数组的背包在遍历顺序上和二维dp数组实现的01背包其实是有很大差异的，大家需要注意！
完全背包
说完01背包，再看看完全背包。
先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。
但是仅仅是纯完全背包的遍历顺序是这样的，题目稍有变化，两个for循环的先后顺序就不一样了。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
相关题目如下：
- 求组合数：动态规划：518.零钱兑换II(opens new window)
- 求排列数：动态规划：377. 组合总和 Ⅳ (opens new window)、动态规划：70. 爬楼梯进阶版（完全背包）(opens new window)
如果求最小数，那么两层for循环的先后顺序就无所谓了，相关题目如下：
对于背包问题，其实递推公式算是容易的，难是难在遍历顺序上，如果把遍历顺序搞透，才算是真正理解了。
3.打家劫舍
198. 打家劫舍
//状态转移方程 当前最大值取决于前一个偷不偷 dp[i]为最大值
//dp[i] = max(dp[i-1],dp[i-2] + nums[i])
class Solution {
public:
int rob(vector<int>& nums) {
if (nums.size() == 0) return 0;
if (nums.size() == 1) return nums[0];
if (nums.size() == 2) return max(nums[0],nums[1]);
vector<int> dp(nums.size(),0);
dp[0] = nums[0];
dp[1] = max(nums[0],nums[1]);
for (int i = 2; i < nums.size(); ++i) {
dp[i] = max(dp[i-1],dp[i-2] + nums[i]);
}
return dp.back();
}
};
213. 打家劫舍 II
//213. 打家劫舍 II
//和I 一样 去掉前后两个元素分别比较
class Solution {
public:
int rob(vector<int>& nums)
{
if(nums.size() == 1)return nums[0];
vector<int> s(nums.begin()+1,nums.end());
vector<int> s2(nums.begin(),nums.end()-1);
return max(getmax(s),getmax(s2));
}
int getmax(vector<int>& nums) {
int dp[102] = {0};
for (int i = 2; i <= nums.size() + 1; ++i) {
dp[i] = max(dp[i-1],dp[i-2] + nums[i - 2]);
}
return dp[nums.size() + 1];
}
};
337. 打家劫舍 III
动态规划其实就是使用状态转移容器来记录状态的变化，这里可以使用一个长度为2的数组，记录当前节点偷与不偷所得到的的最大金钱。这道题目算是树形dp的入门题目（注意用后序遍历的方式推导）
class Solution {
vector<int> find(TreeNode* root)
{
//0 - 偷 1 - 不偷
if(!root) return {0,0};
vector<int> l = find(root->left);
vector<int> r = find(root->right);
//偷
return {l[1] + r[1] + root->val , max({l[0] + r[0],l[0] + r[1],l[1] + r[0],l[1] + r[1]})};
}
public:
int rob(TreeNode* root) {
vector<int> res = find(root);
return max(res[0],res[1]);
}
};
4.买股票
121. 买卖股票的最佳时机
1.确定状态dp【i】【0】为第i天持有股票，包括买入。dp【i】【1】为没有股票，包括没买和卖出
2.初始化{-prices[0],0}
3.状态转移，dp【i】【0】 = 前一天持有股票 和今天买入股票的最大值。dp【i】【1】 = 前一天不买股票和今天卖出股票的最大值
4.最后一定是dp【i】【1】不持有股票的状态
class Solution {
public:
int maxProfit(vector<int>& prices) {
//dp[i][0] 持有 dp[i][1] 不持有
vector<vector<int>> dp(prices.size(),{0,0});
//持有包括一直持有和刚刚买入 ， 不持有包括卖出和不持有
dp[0][0] = -prices[0];
for (int i = 1; i < prices.size(); ++i) {
dp[i][0] = max(dp[i-1][0],-prices[i]);
dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i]);
}
return dp.back()[1];
}
};
122. 买卖股票的最佳时机 II
1.确定状态dp【i】【0】为第i天持有股票，包括买入。dp【i】【1】为没有股票，包括没买和卖出
2.初始化{-prices[0],0}
3.状态转移，dp【i】【0】 = 前一天持有股票 和今天买入股票的最大值。dp【i】【1】 = 前一天不买股票和今天卖出股票的最大值
4.最后一定是dp【i】【1】不持有股票的状态
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.size() < 2) return 0;
vector<vector<int>> dp(prices.size() , {0,0});
dp[0][0] = -prices[0];
for (int i = 1; i < prices.size(); ++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.back()[1];
}
};
123. 买卖股票的最佳时机 III
1.确定状态dp【i】【0】为第一次第i天持有股票，包括买入。dp【i】【1】为第一次没有股票，包括没买和卖出，dp【i】【2】为第二次持有股票，dp【i】【3】为第二次没有股票。
2.初始化{-prices[0],0，-prices[0]，0}
3.状态转移，dp【i】【0】 = 第一次前一天持有股票 和今天买入股票的最大值。dp【i】【1】 = 第一次前一天不买股票和今天卖出股票的最大值，dp【i】【2】 = 第二次前一天持有股票 和今天买入股票的最大值。dp【i】【3】 = 第二次前一天不买股票和今天卖出股票的最大值
4.最后一定是dp【i】【3】第二次不持有股票的状态
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.size() < 2) return 0;
vector<vector<int>> dp(prices.size() , {0,0,0,0});
dp[0][0] = -prices[0];//第一次持有
dp[0][2] = -prices[0];//第二次持有
for (int i = 1; i < prices.size(); ++i) {
dp[i][0] = max(dp[i - 1][0] , - prices[i]);//第一次持有
dp[i][1] = max(dp[i - 1][1] , dp[i - 1][0] + prices[i]);//第一次不持有
dp[i][2] = max(dp[i - 1][2] , dp[i - 1][1] - prices[i]);//第二次持有
dp[i][3] = max(dp[i - 1][3] , dp[i - 1][2] + prices[i]);//第二次不持有
}
return dp.back()[3];
}
};
188. 买卖股票的最佳时机 IV
同上，就增加了循环
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if (prices.size() < 2) return 0;
//初始化dp
vector<vector<int>> dp(prices.size() , vector<int>(2 * k , 0));
//初始化 第i次持有股票 为-prices[0]
for (int i = 0; i < k; ++i) {
dp[0][i * 2] = -prices[0];
}
for (int i = 1; i < prices.size(); ++i) {
//第一次持有/不持有
dp[i][0] = max(dp[i - 1][0] , - prices[i]);
dp[i][1] = max(dp[i - 1][1] , dp[i - 1][0] + prices[i]);
//第 2 - k次持有/不持有
for (int j = 1; j < k; ++j) {
dp[i][2 * j] = max(dp[i - 1][2 * j],dp[i - 1][2 * j - 1] - prices[i]);
dp[i][2 * j + 1] = max(dp[i - 1][2 * j + 1] , dp[i - 1][2 * j] + prices[i]);
}
}
return dp.back()[2 * k - 1];
}
};
309. 最佳买卖股票时机含冷冻期
四个状态 -- 0：持有 1：卖出 2：冷冻期 3：不持有可以买入
需要注意的是到0 有3种方式-----0保持，2到0 ，3到0，到1只有一种方式0-1，到2一种方式1-2 ，到三两种方式 保持和 2-3
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.size() < 2) return 0;
vector<vector<int>> dp(prices.size() , {0,0,0,0});
dp[0][0] = -prices[0];//第一次持有
for (int i = 1; i < prices.size(); ++i) {
dp[i][0] = max(dp[i - 1][0] , max(dp[i - 1][3] - prices[i],dp[i - 1 ][2] - prices[i]));//持有
dp[i][1] = dp[i - 1][0] + prices[i];//卖出
dp[i][2] = dp[i - 1][1];//冷冻期
dp[i][3] = max(dp[i - 1][3] , dp[i - 1][2]);//不持有- 可以买入的状态
}
return max(dp.back()[3], max(dp.back()[2],dp.back()[1]));
}
};
714. 买卖股票的最佳时机含手续费
在买入的时候减去手续费
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
if (prices.size() < 2) return 0;
vector<vector<int>> dp(prices.size() , {0,0});
dp[0][0] = -prices[0] - fee;
for (int i = 1; i < prices.size(); ++i) {
dp[i][0] = max(dp[i - 1][0] , dp[i - 1][1] - prices[i] - fee);
dp[i][1] = max(dp[i - 1][1] , dp[i - 1][0] + prices[i]);
}
return dp.back()[1];
}
};
5.子序列问题
300. 最长递增子序列
dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度
位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。
所以：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> dp(nums.size() ,1);
int maxs = 1;
for (int i = 1; i < nums.size(); ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] > nums[j])
dp[i] = max(dp[i],dp[j] + 1);
}
maxs = max(maxs,dp[i]);
}
return maxs;
}
};
674. 最长连续递增序列
//1.贪心解
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
if (nums.size() < 2) return nums.size();
int maxs = 1;
int res = 1;
for (int i = 1; i < nums.size(); ++i) {
if (nums[i] > nums[i - 1]) maxs++;
else maxs = 1;
res = max(res,maxs);
}
return res;
}
};
//2.dp解
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
vector<int> dp(nums.size() ,1);
int maxs = 1;
for (int i = 1; i < nums.size(); ++i) {
if (nums[i] > nums[i - 1]) dp[i] = dp[i - 1] + 1;
maxs = max(maxs,dp[i]);
}
return maxs;
}
};
718. 最长重复子数组
dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp【i】【j】。 （特别注意： “以下标i - 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串 ）。因为要求连续，所以要以dp【i】【j】结尾。
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
int maxs = 0;
vector<vector<int>>dp(nums1.size() + 1,vector<int>(nums2.size() + 1,0));
for (int i = 1; i <= nums1.size(); ++i) {
for (int j = 1; j <= nums2.size(); ++j) {
if (nums1[i-1] == nums2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
maxs = max(maxs,dp[i][j]);
}
}
return maxs;
}
};
1143. 最长公共子序列
同上，因为不要求连续，所以不相等的时候dp【i】【j】要求其i -1 与j -1中最大值。
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
vector<vector<int>>dp(text1.size() + 1,vector<int>(text2.size() + 1,0));
for (int i = 1; i <= text1.size(); ++i) {
for (int j = 1; j <= text2.size(); ++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.back().back();
}
};
1035. 不相交的线
这道题看似复杂，其实就是求最长公共递增子序列，与上一题相似。
class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
vector<vector<int>>dp(nums1.size() + 1,vector<int>(nums2.size() + 1,0));
for (int i = 1; i <= nums1.size(); ++i) {
for (int j = 1; j <= nums2.size(); ++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.back().back();
}
};
53. 最大子数组和
//1.贪心法
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int maxs = INT_MIN;
int cur = 0;
for (int i = 0; i < nums.size(); ++i) {
cur+=nums[i];
maxs = max(maxs,cur);
if (cur < 0) cur = 0;
}
return maxs;
}
};
//2.dp 公式---前一个和dp【i - 1】 + num【i】 与 num【i】的最大值
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int maxs = nums[0];
vector<int>dp(nums.size() , 0);
dp[0] = nums[0];
for (int i = 1; i < nums.size(); ++i) {
dp[i] = max(dp[i-1] + nums[i],nums[i]);
maxs = max(maxs,dp[i]);
}
return maxs;
}
};
673.最长递增子序列的个数
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
if (nums.size() <= 1) return nums.size();
vector<int> dp(nums.size(),1); //记录为以num[i]结束的最长子序列长度
vector<int> count(nums.size(),1); //记录为以num[i]结束的最长子序列长度个数
int maccount = 1;
for (int i = 1; i < nums.size(); ++i) {
for (int j = 0; j < i; ++j) {
if (nums[j] < nums[i])
{
if (dp[j] + 1 > dp[i]) //需要更新dp[i]，以及以j结束的count
{
dp[i] = dp[j] + 1;
count[i] = count[j];
}
else if (dp[j] + 1 == dp[i])//以j结束的最长字符串长度等于i count需要加j
{
count[i] += count[j];
}
}
maccount = max(dp[i],maccount);
}
}
//寻找最长的长度
int res = 0;
for (int i = 0; i < nums.size(); ++i) {
if (dp[i] == maccount) res+=count[i];
}
return res;
}
};
413. 等差数列划分
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums) {
if (nums.size() < 3) return 0;
vector<int> dp(nums.size(),0);
for (int i = 2; i < nums.size(); ++i) {
if (nums[i] - nums[i-1] == nums[i-1] -nums[i-2]) dp[i] = dp[i-1]+1;
}
return std::accumulate(dp.begin(), dp.end(),0);
}
};
6.编辑距离问题
392. 判断子序列
dp方法：记录相同个数，相同则dp等于上一个+1，不同则看j的上一个
//1.双指针法
class Solution {
public:
bool isSubsequence(string s, string t) {
int slow = 0,fast = 0;
while (fast < t.size() && slow < s.size())
{
if (s[slow] == t[fast]) slow++;
fast++;
}
if (s.size() == slow) return true;
return false;
}
};
//2.dp法
class Solution {
public:
bool isSubsequence(string s, string t) {
vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));
for (int i = 1; i <= s.size(); i++) {
for (int j = 1; j <= t.size(); 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];
}
}
if (dp[s.size()][t.size()] == s.size()) return true;
return false;
}
};
115. 不同的子序列
class Solution {
public:
int numDistinct(string s, string t) {
vector<vector<uint64_t>>dp(s.size()+1,vector<uint64_t>(t.size()+1,0));
for (int i = 0; i <= s.size(); ++i) dp[i][0] = 1;
for (int i = 1; i <=s.size() ; ++i) {
for (int j = 1; j <= t.size() ; ++j) {
if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i-1][j-1]+dp[i-1][j];
else dp[i][j] = dp[i-1][j];
}
}
return dp.back().back();
}
};
583. 两个字符串的删除操作
class Solution {
public:
int minDistance(string word1, string word2) {
vector<vector<int>>dp(word1.size()+1,vector<int>(word2.size()+1,0));
for (int i = 0; i <= word2.size(); ++i) dp[0][i] = i;
for (int i = 0; i <= word1.size(); ++i) dp[i][0] = i;
for (int i = 1; i <=word1.size() ; ++i) {
for (int j = 1; j <= word2.size() ; ++j) {
if (word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i-1][j-1];
else dp[i][j] = min(dp[i][j-1]+1, min(dp[i-1][j]+1,dp[i-1][j-1]+2));
}
}
return dp.back().back();
}
};
72. 编辑距离
class Solution {
public:
int minDistance(string word1, string word2) {
vector<vector<int>>dp(word1.size()+1,vector<int>(word2.size()+1,0));
for (int i = 0; i <= word2.size(); ++i) dp[0][i] = i;
for (int i = 0; i <= word1.size(); ++i) dp[i][0] = i;
for (int i = 1; i <=word1.size() ; ++i) {
for (int j = 1; j <= word2.size() ; ++j) {
if (word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i-1][j-1];
else dp[i][j] = min(dp[i][j-1], min(dp[i-1][j],dp[i-1][j-1]))+1;
}
}
return dp.back().back();
}
};
10. 正则表达式匹配
class Solution {
public:
bool isMatch(string s, string p) {
// dp[i][j] 表示 s以i - 1结束，p以j - 1结束是否能匹配 （0 - n）
vector<vector<bool>> dp(s.size() + 1,vector<bool>(p.size()+1, false));
//初始化 dp[0][i] , s字符串为空时，p的*个数
dp[0][0] = true;
for (int i = 1; i <= p.size(); ++i) {
if (p[i - 1] == '*')dp[0][i] = dp[0][i-2];
}
for (int i = 1; i <= s.size(); ++i) {
for (int j = 1; j <= p.size() ; ++j) {
//1.遇到 .
if (p[j - 1] == '.') dp[i][j] = dp[i-1][j-1];
//2.遇到两者相等
else if(p[j - 1] != '*') dp[i][j] = dp[i-1][j-1] && p[j - 1] == s[i - 1];
//3.遇到 p[i - 2] 和s[i-2]不匹配
else if(p[j - 2] != '.' && p[j - 2] != s[i - 1])dp[i][j] = dp[i][j-2];
//其他 ，遇到*
else dp[i][j] = dp[i-1][j]||dp[i][j-1]||dp[i][j-2];
}
}
return dp.back().back();
}
};
7.回文问题
647. 回文子串
class Solution {
public:
int countSubstrings(string s) {
vector<vector<bool>> dp(s.size(),vector<bool>(s.size(),false));
int count = 0;
for (int i = 0; i < s.size(); ++i) dp[i][i] = true;
for (int i = s.size() -1 ; i >= 0; --i) {
for (int j = i; j < s.size(); ++j) {
if (s[i] == s[j] && (j - i <= 1 || dp[i+1][j-1]))
{
count++;
dp[i][j] = true;
}
}
}
return count;
}
};
516. 最长回文子序列
class Solution {
public:
int longestPalindromeSubseq(string s) {
vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
for (int i = 0; i < s.size(); i++) dp[i][i] = 1;
for (int i = s.size() - 1; i >= 0; i--) {
for (int j = i + 1; j < s.size(); 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][s.size() - 1];
}
};
5. 最长回文子串
class Solution {
public:
string longestPalindrome(string s) {
vector<vector<bool>> dp(s.size(),vector<bool>(s.size(), false));
int maxstart,malen=0;
for (int i = s.size()-1; i >=0 ; --i) {
for (int j = i; j < s.size(); ++j) {
if (s[i] == s[j] && (j - i <= 1 || dp[i+1][j-1])) dp[i][j] = true;
if (dp[i][j] && malen < j - i +1)
{
malen = j - i +1;
maxstart = i;
}
}
}
return s.substr(maxstart,malen);
}
};
132. 分割回文串 II
class Solution {
public:
int minCut(string s) {
vector<vector<bool>>dp(s.size(),vector<bool>(s.size(), false));
for (int i = s.size() - 1; i >= 0 ; --i) {
for (int j = i; j < s.size(); ++j) {
if (s[i] == s[j] && (j - i <= 2 || dp[i+1][j-1]))dp[i][j] = true;
}
}
vector<int> res(s.size());
for (int i = 0; i < s.size(); ++i) res[i] = i;
for (int i = 1; i < s.size(); ++i) {
if (dp[0][i])
{
res[i] = 0;
continue;
} else
{
for (int j = 0; j < i; ++j) {
if (dp[j+1][i]) res[i] = min(res[i],res[j]+1);
}
}
}
return res.back();
}
};