【代码随想录】二刷-动态规划
动态规划
解题步骤:
- 确定dp数组
- 确定递推公式——递推公式决定dp数组要如何初始化
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
509. 斐波那契数
class Solution {
public:
int fib(int n) {
if(n <= 1)return n;
// 推导公式: dp[n] = dp[n-1]+dp[n-2]
int dp[2];
// 初始化
dp[0] = 0;
dp[1] = 1;
// 从前往后
for(int i = 2; i <= n;i++){
int tmp = dp[0] + dp[1];
dp[0] = dp[1];
dp[1] = tmp;
}
return dp[1];
}
};70. 爬楼梯
class Solution {
public:
int climbStairs(int n) {
if(n <= 2)return n;
// dp[n] = d[n-1] + dp[n-2]
int dp[2];
dp[0] = 1;// 1阶楼梯-1种方法
dp[1] = 2;// 2阶楼梯-2种方法
for(int i = 3; i <= n;i++){
int tmp = dp[1] + dp[0];
dp[0] = dp[1];
dp[1] = tmp;
}
return dp[1];
}
};746. 使用最小花费爬楼梯
// 时间复杂度O(n)
// 空间复杂度O(n)
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
// 到达第i阶台阶的最少花费
vector<int>dp(cost.size()+1,0);
// 可以选择从0阶或1阶开始爬，所以初始化0 1阶都为0
dp[0] = 0;
dp[1] = 0;
for(int i = 2; i <= cost.size();i++){
dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);// 递推公式
}
return dp[cost.size()];
}
};62. 不同路径
- 二维数组
// 时间复杂度O(mxn)
// 空间复杂度O(mxn)
class Solution {
public:
int uniquePaths(int m, int n) {
// dp[i][j]: 到达i j点，有多少种方法
vector<vector<int>>dp(m,vector<int>(n,0));
// 初始化-第一行只有一条路径,注: 小叮当每次只能向下或者向上进行移动
for(int i = 0; i < n;i++)dp[0][i] = 1;
// 初始化-第一列只有一条路径
for(int i = 0; i < m;i++)dp[i][0] = 1;
// 遍历顺序，从1,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];
}
};
- 滚动数组
// 时间复杂度O(mxn)
// 空间复杂度O(m)
class Solution {
public:
int uniquePaths(int m, int n) {
vector<int>dp(n,0);
for(int i = 0; i< n;i++)dp[i] = 1;
// 相当于每行开始就已经把上放的加到自己上面了，遍历的时候只需要将左边的加上即可
for(int i = 1; i < m;i++){
for(int j = 1; j < n;j++){
dp[j] += dp[j-1];
}
}
return dp[n-1];
}
};63. 不同路径 II
// 时间复杂度O(mxn)
// 空间复杂度O(mxn)
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& ob) {
int m = ob.size();//行
int n = ob[0].size();// 列
// 如果起点 or 终点出现障碍，直接返回
if(ob[0][0] == 1 ||ob[m-1][n-1] == 1)return 0;
// dp[i][j]: 到i j点有多少种路径
vector<vector<int>>dp(m,vector<int>(n,0));
// 初始化同上一题，但是注意，左边为障碍物，后面就都是0了
for(int i = 0; i < n && ob[0][i] == 0;i++)dp[0][i] = 1;
// 初始化-同上说明
for(int i = 0; i < m && ob[i][0] == 0;i++)dp[i][0] = 1;
// 遍历顺序: 从1,1 点出发
for(int i = 1; i < m;i++){
for(int j = 1;j < n;j++){
if(ob[i][j] == 1)continue;
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
};
- 滚动数组
// 时间复杂度O(mxn)
// 空间复杂度O(m)
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& ob) {
if(ob[0][0] == 1 || ob[ob.size()-1][ob[0].size()-1] == 1)return 0;
vector<int>dp(ob[0].size(),0);
// 初始化第一行
for(int i = 0; i < dp.size();i++){
if(ob[0][i] == 1)dp[i] = 0;// 障碍
else if(i == 0)dp[i] = 1;
else dp[i] = dp[i-1];// 过不来了
}
for(int i = 1;i < ob.size();i++){
for(int j = 0; j < dp.size();j++){
if(ob[i][j] == 1)dp[j] = 0;// 障碍
else if(j != 0)dp[j]+= dp[j-1];// !=0 防止越界
// 相当于每行开始就已经把上放的加到自己上面了，遍历的时候只需要将左边的加上即可
}
}
return dp[dp.size()-1];
}
};343. 整数拆分
// 时间复杂度O(n^2)
// 空间复杂度O(n)
class Solution {
public:
int integerBreak(int n) {
// dp[i]: 数字i可以得到的最大乘积
vector<int>dp(n+1);
// 初始化
dp[2] = 1;
// 遍历顺序
for(int i =3; i <= n;i++){
for(int j = 1; j < i-1;j++){// 可以优化为j <= i /2 因为拆分成最大，应该是两个近似相同的数
// 多次计算，所以要和dp[i]比较
dp[i] = max(dp[i],max((i-j)*j,dp[i-j]*j));// 递归公式，当前两个数 or 接着拆分取最大乘
}
}
return dp[n];
}
};96. 不同的二叉搜索树
// 时间复杂度: O(n^2)
// 空间复杂度: O(n)
class Solution {
public:
int numTrees(int n) {
// dp[i]: 用值为1-i的i个节点组成的二叉搜索树的个数为dp[i]
vector<int>dp(n+1);
// 初始化-空节点组成的二叉搜索树只有一种
dp[0] = 1;
for(int i = 1;i <= n;i++){
for(int j = 1; j <= i;j++){
dp[i] += dp[j-1]*dp[i-j];// 递推公式
}
}
return dp[n];
}
};背包问题
01背包
前言
- 什么是01背包?
- 有n件物品和一个最多能背重量为w的背包。第i件物品的重量是weight[i]，得到的价值是value[i]。
- 每个件物品只能用一次，求解将哪些物品装入背包里的物品总价值最大。
- 即，每件物品只有选或不选两种情况
- 二维dp数组01背包
- dp[i][j]: 表示从下标为0-i的物品里任意取，放进容量为j的背包，价值总和最大是多少。从两个方向推出来:
- 不放物品i: 由dp[i-1][j]推出，即不放当前物品i，最大价值就是前面判断出来的。——即当前容量不够i的了，最大值还是之前的。
- 放物品i: 由dp[i-1][j-weight[i]]推出，即先求出不放物品i可以达到的最大值，完了再加上物品i的价值，求得放物品i可以达到的最大值。
- dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
- 如何初始化
- 根据dp数组的定义进行初始化
- dp[0] = 0
- dp[0][j]: 放第0件物品容量为j的最大值，value[0] > j 值为0，反之为value[0]
- 确定遍历顺序
- 先遍历物品or背包都可以，但是先遍历物品更好理解
- 先遍历物品: 尝试将每个物品放到每个背包中，求得背包最大值。
- 先遍历背包: 背包i依次尝试每个物品，求得背包最大值。
- 补充: 动态规划：关于01背包问题，你该了解这些！
- 滚动数组： 压缩空间
- 将上一层的拷贝下来，递推公式变为:
- dp[i][j] = max(dp[i][j],dp[i][j-weight[i]]+value[i])
- 需要满足的条件是上一层可以重复利用
- 推导出使用一维dp数组：
- dp数组含义
- dp[j]: 容量为j的背包，所背物品价值最大可以为dp[j]
- 递推公式
- 通过dp[j-weight[i]]推导，dp[j-weight[i]]+value[i]为不装i可到达的最大价值+物品i的价值，当前背包放入物品i达到的最大价值
- dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);取大的，不放物品i为dp[j],放物品i为后者。
- 初始化
- 注意要与定义相吻合
- dp数组在推导的时候取大值，不能被初始值覆盖，所以初始化为0即可。
- 遍历顺序
- 先正序遍历物品，然后倒序遍历背包
- 倒序遍历背包防止物品被加入多次
- 为什么二维dp就不需要倒序？
- 因为二维dp的值是通过上一层计算而来，不会覆盖本层。
- 注: 不能先遍历背包，这会导致每个背包只会被放入一个物品。
- 以下的题都要转化为背包问题
416. 分割等和子集
// 时间复杂度 O(n^2)
// 空间复杂度 O(n)
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(),nums.end(),0);
if(sum % 2 == 1)return false;// 整数，所以出现小数分不开
int target = sum/2;// 背包大小
vector<int>dp(target+1,0);
dp[0] = 0;// 初始化，容量为0的背包，可累加最大值为0.
for(int i = 0; i < nums.size();i++){// 物品
for(int j = target;j >= nums[i];j--){// 背包
dp[j] = max(dp[j],dp[j-nums[i]]+nums[i]);// 推导
}
}
// 成功找到了目标值，即可以分成两组
if(dp[target] == target)return true;
return false;
}
};1049. 最后一块石头的重量 II
// 时间复杂度: O(mxn)
// 空间复杂度: O(m)
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
// 类似于上一题，将石头分为了两堆，用全部重量减去这两堆看还能省多少，就是结果
// 转换了一下
int sum = accumulate(stones.begin(),stones.end(),0);
int target = sum / 2;
vector<int>dp(target+1,0);
dp[0] = 0;
for(int i = 0; i < stones.size();i++){
for(int j = target; j >= stones[i];j--){
dp[j] = max(dp[j],dp[j-stones[i]]+stones[i]);
}
}
return sum - dp[target]-dp[target];
}
};494. 目标和
// 时间复杂度：O(n × m)，n为正数个数，m为背包容量
// 空间复杂度：O(m)，m为背包容量
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
// 转换为填满x的背包有几种方法
// 表达式加法总和为x,减法总和sum-x
// x-(sum-x)= target
// 即 x = (target+sum)/2
int sum = accumulate(nums.begin(),nums.end(),0);
// 两种没有方案的情况
if(abs(target) > sum)return 0;
if((target + sum) % 2 == 1)return 0;
int tag = (target + sum)/2;
vector<int>dp(tag+1,0);
dp[0] = 1;// 没有实际意义，递推公式推导所得
for(int i = 0; i < nums.size();i++){
for(int j = tag;j >= nums[i];j--){
dp[j] += dp[j-nums[i]];// 组合问题-递推公式
}
}
return dp[tag];
}
};474. 一和零
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
// dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
vector<vector<int>>dp(m+1,vector<int>(n+1,0));
for(string& str: strs){
int oneCnt = 0;
int zeroCnt = 0;
for(char& c: str){
if(c == '0')zeroCnt++;
else oneCnt++;
}
// 两个维度都是背包容量，一个是1 一个是0
// 遍历到时候相当于两个滚动数组，后序遍历两个容量
for(int i = m; i >= zeroCnt;i--){
for(int j = n; j >= oneCnt;j--){
// 递推公式
dp[i][j] = max(dp[i][j],dp[i-zeroCnt][j-oneCnt]+1);
}
}
}
return dp[m][n];
}
};完全背包
前言
- 与01背包不同的是，完全背包中，每种物品有无限件。
- 遍历时，内层的背包容量遍历，要从小到大遍历。
- 尽管在一维dp数组中，完全背包的遍历顺序也是无所谓的，这里指的是先遍历容器还是先遍历物品。
- 依然注意下面问题的转换
518. 零钱兑换 II
class Solution {
public:
int change(int amount, vector<int>& coins) {
// 凑成总金额j的货币组合数为dp[j]
vector<int>dp(amount+1,0);
dp[0] = 1;// 初始化—凑合为0金额，有一种
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];
}
};
- 补充:
- 组合数外层for循环遍历物品，内层遍历背包
- 排列数外层for循环背包，内层遍历物品
377. 组合总和 Ⅳ
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
// 凑成i的排列组合个数为dp[i]
vector<int>dp(target+1,0);
// 初始化，从前一个得出，可以说没有一起
dp[0] = 1;
// 求组合，先遍历背包
for(int i = 0 ;i <= target ;i++){
for(int j = 0; j < nums.size();j++){
// 有个册数用例相加超过intg
if(i - nums[j] >= 0 && dp[i] < INT_MAX - dp[i-nums[j]]){
dp[i] += dp[i-nums[j]];
}
}
}
return dp[target];
}
};70. 爬楼梯
class Solution {
public:
int climbStairs(int n) {
// 爬i阶台阶，dp[i]种方法
vector<int>dp(n+1,0);
dp[0] = 1;/
for(int i = 1;i <= n ;i++){// 背包
for(int j = 1; j <= 2;j++){// 物品
if(i - j >= 0)dp[i] += dp[i-j];// 求排列
}
}
return dp[n];
}
};322. 零钱兑换
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
// 组成金额i,所需要的最少硬币数为dp[i]
vector<int>dp(amount+1,INT_MAX);
dp[0] = 0;//凑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. 完全平方数
class Solution {
public:
int numSquares(int n) {
// 和为i的最少完全平方数为dp[i]
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],dp[i-j*j]+1);// 递推公式
}
}
return dp[n];
}
};139. 单词拆分
// 时间复杂度: O(n^3)
// 空间复杂度: O(n)
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
// 将字典存到哈希表中，便于使用
unordered_set<string>set(wordDict.begin(),wordDict.end());
// dp[i],长度为i的字符串，是否可以由字典组成
vector<bool>dp(s.size()+1,false);
dp[0] = true;// 空字符串，肯定可以组成
// 求排列-先背包-再物品
for(int i = 1; i <= s.size() ;i++){// 背包
for(int j = 0; j < i;j++){// 物品-遍历截取s
string word = s.substr(j,i-j);
// 该字串在字典中，并且组成的前一段子串也在字典中
// 0到j和j到j+i-j,组成这个子串
if(set.find(word) != set.end() && dp[j])dp[i] = true;
}
}
return dp[s.size()];
}
};打家劫舍问题
198. 打家劫舍
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
if (n == 1) return nums[0];
// dp[i]: 下标i内包括i，可以偷的最高金额是dp[i]
vector<int>dp(n,0);
// 初始化
dp[0] = nums[0];
dp[1] = max(nums[0],nums[1]);
// 遍历
for(int i = 2 ; i < n; i++){
// 两种情况：
// 不偷当前这家，考虑前一家
// 偷当前这家，累加上i-2这家
// 也就是偷或者不偷，偷累加当前与i-2,不偷还取前一家可以去的最大值。
dp[i] = max(dp[i-2]+nums[i],dp[i-1]);
}
return dp[n-1];
}
};213. 打家劫舍 II
class Solution {
public:
// 同上一题，只是增加的范围的讨论
int range(vector<int>& nums,int start,int end){
if(start == end)return nums[start];
vector<int>dp(nums.size());
dp[start] = nums[start];
dp[start+1] = max(nums[start],nums[start+1]);
for(int i = start + 2;i <= end;i++){
dp[i] = max(dp[i-2]+nums[i],dp[i-1]);
}
return dp[end];
}
int rob(vector<int>& nums) {
// 分为三种情况:
// 1 不考虑头尾，
// 2 考虑头，不考虑尾
// 3 考虑尾，不考虑头
// 考虑为有可能会用到，并不是一定要用
// 情况1已经被包括在2 3 中
// 所以值考虑后两种情况即可
int n = nums.size();
if(n == 0)return 0;
if(n == 1)return nums[0];
int ret1 = range(nums,0,n-2);
int ret2 = range(nums,1,n-1);
return max(ret1,ret2);
}
};337. 打家劫舍 III
// 时间复杂度：O(n)，每个节点只遍历了一次
// 空间复杂度：O(log n)，算上递推系统栈的空间
class Solution {
public:
// 注意: 0-为偷情况，1-为不偷情况
vector<int>robTree(TreeNode* cur){
if(!cur)return vector<int>{0,0};
// 后序遍历
vector<int>left = robTree(cur->left);
vector<int>right = robTree(cur->right);
// 中-单层递归逻辑
//偷当前结点：当前val+左右不偷情况
int val1 = cur->val + left[0]+right[0];
// 不偷当前结点: 左右取大的去情况相加
int val2 = max(left[0],left[1])+max(right[0],right[1]);
return {val2,val1};
}
int rob(TreeNode* root) {
auto ret = robTree(root);
return max(ret[0],ret[1]);
}
};
- 记忆化递推
// 后序遍历
class Solution {
public:
unordered_map<TreeNode* , int> umap;
int rob(TreeNode* root) {
if(!root)return 0;
if(!root->left && !root->right)return root->val;
if(umap[root])return umap[root];
int val1 = root->val;
// 偷父结点: 去累加孩子的孩子
if(root->left) val1 += rob(root->left->left) + rob(root->left->right);
if(root->right) val1 += rob(root->right->left) + rob(root->right->right);
// 不偷父结点
int val2 = rob(root->left)+rob(root->right);
umap[root] = max(val1,val2);
return max(val1,val2);
}
};买卖股票问题
121. 买卖股票的最佳时机
// 时间复杂度：O(n)
// 空间复杂度：O(n)
class Solution {
public:
int maxProfit(vector<int>& prices) {
// dp[i][0] 表示第i天不持有股票所得最多现金
// dp[i][1] 表示第i天持有股票所得最多现金
vector<vector<int>>dp(prices.size(),vector<int>(2,0));
dp[0][0] = 0;// 不持有-卖出
dp[0][1] -= prices[0];// 持有-买入
for(int i = 1 ; i < prices.size();i++){
// 不持有当天股票: 保持现状or卖出-之前持有状态+当天股票价格 = 卖出
// 可以理解为，之前所获得的最大利润和当天卖出可获得的利润
// 当天可获得的利润为: 之前找到的最小的买入值，与今天的价格进行求利润
dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i]);
// 持有(买入)当天股票: 保持现状-之前买入的状态 or 今天买入，选大的
// 可以理解为找更小的买入
dp[i][1] = max(dp[i-1][1],-prices[i]);
}
return dp[prices.size()-1][0];// 卖出的状态肯定的大
}
};
- 空间优化
// 时间复杂度：O(n)
// 空间复杂度：O(1)
class Solution {
public:
int maxProfit(vector<int>& prices) {
// dp[i][0] 表示第i天不持有股票所得最多现金
// dp[i][1] 表示第i天持有股票所得最多现金
vector<vector<int>>dp(2,vector<int>(2,0));
dp[0][0] = 0;// 不持有-考虑卖出
dp[0][1] -= prices[0];// 持有-考虑买入
for(int i = 1 ; i < prices.size();i++){
// 不持有当天股票: 保持现状or卖出-之前持有状态+当天股票价格 = 卖出
dp[i % 2][0] = max(dp[(i-1)%2][0],dp[(i-1)%2][1]+prices[i]);
// 持有(买入)当天股票: 保持现状-之前买入的状态 or 今天买入，选大的
dp[i%2][1] = max(dp[(i-1)%2][1],-prices[i]);
}
return dp[(prices.size()-1)%2][0];// 卖出的状态肯定的大
}
};122. 买卖股票的最佳时机 II
// 时间复杂度：O(n)
// 空间复杂度：O(n)
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
vector<vector<int>>dp(n,vector<int>(2,0));
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];
}
};123. 买卖股票的最佳时机 III
// 时间复杂度：O(n)
// 空间复杂度：O(n × 5)
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
vector<vector<int>>dp(n,vector<int>(5,0));
// 分两次买的情况，买卖或者延续之前的状态
// 五种情况
/*
0 没有操作 （其实我们也可以不设置这个状态）
1 第一次持有股票
2 第一次不持有股票
3 第二次持有股票
4 第二次不持有股票
*/
dp[0][0] = 0;
dp[0][1] -= prices[0];
dp[0][2] = 0;
dp[0][3] -= prices[0];
dp[0][4] = 0;
for(int i = 1;i < n;i++){
// 注意: 在前一天的基础上
dp[i][0] = dp[i-1][0];
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]);
dp[i][4] = max(dp[i-1][4],dp[i-1][3]+prices[i]);
}
return dp[n-1][4];
}
};188. 买卖股票的最佳时机 IV
// 上一题的进阶版，根据2*k+1讨论奇偶情况，卖出还是买入
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
vector<vector<int>>dp(n,vector<int>(2*k+1,0));
// 初始化-奇数次的情况-即考虑买入情况
// 注意边界控制
for(int i = 1; i < 2*k+1;i += 2){
dp[0][i] = -prices[0];
}
for(int i = 1;i < n;i++){
// 小于2*k -1防止+2越界
for(int j = 0; j < 2*k-1;j += 2){
// 考虑买入情况
dp[i][j+1] = max(dp[i-1][j+1],dp[i-1][j]-prices[i]);
// 考虑卖出情况，注意+1,在之前的买入状态上再卖出
dp[i][j+2] = max(dp[i-1][j+2],dp[i-1][j+1]+prices[i]);
}
}
// 最后一考虑卖出状态为最大值
return dp[n-1][2*k];
}
};309. 最佳买卖股票时机含冷冻期
//时间复杂度：O(n)
//空间复杂度：O(n)
class Solution {
public:
int maxProfit(vector& prices) {
int n = prices.size();
vector>dp(n,vector(4,0));
/*
0- 持有股票状态-考虑买入
- 昨天就是买入状态
- 昨天保持卖出状态，一直还没进行之后的买入
- 昨天冷冻期
1- 保持卖出股票状态
- 保持考虑卖出状态，即买入了在等待卖出
- 昨天的冷冻期
2- 今天卖出
- 取到昨天考虑卖出的情况
3- 今天为冷冻期
- 取作品卖出情况
*/
dp[0][0] -= prices[0];
dp[0][1] = 0;
dp[0][2] = 0;
dp[0][3] = 0;
for(int i = 1; i < n;i++){
// 持有股票: 之前的买入状态， or 选取一个之前大的状态然后买入今天的
dp[i][0] = max(dp[i-1][0],max(dp[i-1][1],dp[i-1][3])-prices[i]);
// 保持之前的卖出状态，卖出状态 or 冷冻期
dp[i][1] = max(dp[i-1][1],dp[i-1][3]);
// 卖出: 之前的买入状态+当前的价格=卖出
dp[i][2] = dp[i-1][0]+prices[i];
// 冷冻期: 保持之前的卖出状态
dp[i][3] = dp[i-1][2];
}
return max(dp[n-1][3],max(dp[n-1][2],dp[n-1][1]));
}
}; 714. 买卖股票的最佳时机含手续费
// 时间复杂度：O(n)
// 空间复杂度：O(n)
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
// II的升级版，增加手续费，在卖出的时候，防止多次计算
int n = prices.size();
vector<vector<int>>dp(n,vector<int>(2,0));
// 不持有-考虑卖出
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]-fee);
dp[i][1] = max(dp[i-1][1],dp[i-1][0]-prices[i]);
}
return max(dp[n-1][1],dp[n-1][0]);
}
};子序列问题
300. 最长递增子序列
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
// dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度
int n = nums.size();
if(n <= 1)return n;
int ret = 0;
vector<int>dp(n,1);// 初始化
for(int i =1 ; i < n ; i++){
for(int j = 0; j < i ;j++){
if(nums[i] > nums[j])dp[i] = max(dp[i],dp[j]+1);// 递增序列
}
if(dp[i] > ret)ret = dp[i];// 收集大值
}
return ret;
}
};674. 最长连续递增序列
// 时间复杂度：O(n)
// 空间复杂度：O(n)
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
int n = nums.size();
if(n <= 1)return n;
// dp[i]：以下标i为结尾的连续递增的子序列长度为dp[i]。
int ret = 0;
vector<int>dp(n,1);
for(int i = 1; i < n; i++){
if(nums[i] > nums[i-1]){
dp[i] = dp[i-1]+1;
}
ret = max(ret,dp[i]);
}
return ret;
}
};718. 最长重复子数组
// 时间复杂度：O(n × m)，n 为A长度，m为B长度
// 空间复杂度：O(n × m)
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
// 以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]
int n1 = nums1.size();
int n2 = nums2.size();
int ret = 0;
vector<vector<int>>dp(n1+1,vector(n2+1,0));
// 遍历
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;
}
if(dp[i][j] > ret)ret = dp[i][j];
}
}
return ret;
}
};
- 空间优化
//时间复杂度：$O(n × m)$，n 为A长度，m为B长度
//空间复杂度：$O(m)$
class Solution {
public:
// 到i-1,统一处理所有情况
int findLength(vector<int>& nums1, vector<int>& nums2) {
int n1 = nums1.size();
int n2 = nums2.size();
vector<int>dp(n1+1,0);
int ret = 0;
for(int i = 1 ; i <= n1; i++){
for(int j = n2; j > 0; j--){// 反着遍历b避免重复覆盖
if(nums1[i-1] == nums2[j-1]){
dp[j] = dp[j-1]+1;
}else dp[j] = 0;// 注意这里不等时的赋0操作
if(dp[j]> ret)ret = dp[j];
}
}
return ret;
}
};1143. 最长公共子序列
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
//dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]
int n1 = text1.size();
int n2 = text2.size();
vector<vector<int>>dp(n1+1,vector<int>(n2+1,0));
for(int i = 1 ; i <= n1; i++){
for(int j = 1; j <= n2; 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[n1][n2];
}
};1035. 不相交的线
// 转化题意，数字的相对顺序不改变即可，还是求最长公共序列的长度，可以不连续，同上
class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
int n1 = nums1.size();
int n2 = nums2.size();
vector<vector<int>>dp(n1+1,vector<int>(n2+1,0));
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];
}
};53. 最大子数组和
// 时间复杂度：O(n)
// 空间复杂度：O(n)
class Solution {
public:
int maxSubArray(vector<int>& nums) {
// dp[i]：包括下标i之前的最大连续子序列和为dp[i]。
int n = nums.size();
vector<int>dp(n,0);
dp[0] = nums[0];
int ret = dp[0];// 收集最大结果
// 遍历顺序
// 由两个方向可以推出，之前的加上自己的，或是从自己这里重新开始
for(int i = 1 ;i < n;i++){
dp[i] = max(dp[i-1]+nums[i],nums[i]);// 递推公式-从这里两个中收集大的，会改变值，所以要有个额外变量来收集结果
if(dp[i] > ret)ret = dp[i];
}
return ret;
}
};编辑距离
392. 判断子序列
// 时间复杂度：O(n × m)
// 空间复杂度：O(n × m)
// 同上，不同之处在于，不同时，往回调整t
class Solution {
public:
bool isSubsequence(string s, string t) {
// 问题转化，求最长公共子序列
// 最后看长度是否等于s
int n1 = s.size();
int n2 = t.size();
// dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，最大相同子序列的长度为dp[i][j]。
vector<vector<int>>dp(n1+1,vector<int>(n2+1,0));
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];// 注意这里，不同时往回调整t
}
}
return dp[n1][n2] == n1;
}
};115. 不同的子序列
class Solution {
public:
int numDistinct(string s, string t) {
// 也要求不用连续
// 在上题基础上，不找t与s的最长相等子序列了，找t的子序列在s中出现的个数
int n1 = s.size();
int n2 = t.size();
// dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
vector<vector<uint64_t>>dp(n1+1,vector<uint64_t>(n2+1,0));
// 以i-1为结尾的s可以随便删除元素，出现空字符串的个数。
// 删光s出现1次空字符串，包含啦
for(int i = 0; i < n1;i++)dp[i][0] = 1;
// 空字符串s可以随便删除元素，出现以j-1为结尾的字符串t的个数。
// 空s可肯定不包括t中任何子序列
//for(int i = 1; i < n2;i++)dp[0][i] = 0;// 其实dp数组初始化时已经赋值完成
// 遍历顺序
for(int i = 1 ; i <= n1 ;i++){
for(int j = 1; j <= n2; j++){
// 因为要计算t的子序列出现在s中的个数，所以类加上之前的状态dp[i-1][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];// 调整s
}
}
return dp[n1][n2];
}
};583. 两个字符串的删除操作
class Solution {
public:
int minDistance(string word1, string word2) {
// 以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。
int n1 = word1.size();
int n2 = word2.size();
vector<vector<int>>dp(n1+1,vector<int>(n2+1,0));
// 初始化
// word1删除几次与空字符串相等
for(int i = 0; i <= n1;i++)dp[i][0] = i;
// word2删除几次与空字符串相等
for(int i = 0; i <= n2;i++)dp[0][i] = i;
for(int i = 1; i <= n1;i++){
for(int j = 1; j <= n2;j++){
if(word1[i-1] == word2[j-1]){// 相等，不用增加删除次数
dp[i][j] = dp[i-1][j-1];
// 不等情况，删除word1[i-1],删除word2[j-1],值+1,或都删除，值为上一种情况+2
}else dp[i][j] = min(dp[i-1][j-1]+2,min(dp[i][j-1],dp[i-1][j])+1);
}
}
return dp[n1][n2];
}
};
- 或是同1143，求得两个最长公共前后缀，然后用两个字符串的长度减去即可
class Solution {
public:
int minDistance(string word1, string word2) {
// 以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，最长相等子序列
int n1 = word1.size();
int n2 = word2.size();
vector<vector<int>>dp(n1+1,vector<int>(n2+1,0));
int ret = 0;
for(int i = 1; i <= n1;i++){
for(int j = 1; j <= n2;j++){
if(word1[i-1] == word2[j-1]){
dp[i][j] = dp[i-1][j-1]+1;// 相等长度+1
}else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}
}
// 求得两个最长公共前后缀，然后用两个字符串的长度减去即可,求得要删除的次数
return n1+n2-dp[n1][n2]*2;
}
};72. 编辑距离
// 添加操作同删除操作，这个增加一个，相当于另一个减少，替换操作,可以想象成，之前的已经都判断相等了，求得使得相等的最少操作次数了，这里不等了，在就替换这个字符，即+1步
class Solution {
public:
int minDistance(string word1, string word2) {
// dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。
// 即使得到word[i-1] word2[i-1]两个字符串相等的最少操作数为多少。
int n1 = word1.size();
int n2 = word2.size();
vector<vector<int>>dp(n1+1,vector<int>(n2+1,0));
// 初始化同一题
for(int i = 0; i <= n1;i++)dp[i][0] = i;
for(int i = 0; i <= n2;i++)dp[0][i] = i;
for(int i = 1 ;i <= n1; i++){
for(int j = 1; j <= n2;j++){
if(word1[i-1] == word2[j-1]){// 相等，不需要操作
dp[i][j] = dp[i-1][j-1];
// 一个删除操作，就相当于另一个增加操作
}else dp[i][j] = min(min(dp[i][j-1]+1,dp[i-1][j]+1),dp[i-1][j-1]+1);//1可以提出来
// dp[i][j] = min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]})+1;
}
}
return dp[n1][n2];
}
};647. 回文子串
// 时间复杂度：O(n^2)
// 空间复杂度：O(n^2)
class Solution {
public:
int countSubstrings(string s) {
// 表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。
int n = s.size();
// 初始化false
vector<vector<bool>>dp(n,vector<bool>(n,false));
int ret = 0;
// 注意遍历顺序以及下面的if else 判断以此用到之前的求出的结果
// i从尾部开始控制start,j从i开始控制end到n-1(字符串结尾)
for(int i = n-1; i >= 0;i--){
for(int j = i; j < n ;j++){
// 下面两种情况可以简化简化一下代码
if(s[i] == s[j]){
if(j - i <= 1){// i j指向同一个元素，或为两个相邻元素
ret++;
dp[i][j] = true;
}else if(dp[i+1][j-1]){// i j 距离相差大于1，看里面的区间是否是回文子串
ret++;
dp[i][j] = true;
}
}
}
}
return ret;
}
};
- 双指针
- 从中心点开始扩散，一个值可以作为中心点，两个点也可以作为中心点
// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
class Solution {
public:
// 从中心点开始扩散，一个值可以作为中心点，两个点也可以作为中心点
int extend(const string& s,int i ,int j,int n){
int ret = 0;
while(i >= 0 && j < n && s[i] == s[j]){
i--;
j++;
ret++;
}
return ret;
}
int countSubstrings(string s) {
int ret =0 ;
int n = s.size();
for(int i = 0; i < n ; i++){
ret += extend(s,i,i,n);// 一个点做中心点
ret += extend(s,i,i+1,s.size());// 两个点做中心点
}
return ret;
}
};516. 最长回文子序列
class Solution {
public:
int longestPalindromeSubseq(string s) {
// 字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]
int n = s.size();
vector<vector<int>>dp(n,vector<int>(n,0));
// 初始化,一个字符，最长回文子串就是1
for(int i = 0;i < n;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;// 两个字符相等，+2长度
}else{// 不等，取之前大的
// 如果s[i]与s[j]不相同，说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子串的长度，
// 那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。
// 为什么不比较下dp[i+1][j-1]，因为已经包含在里面了
dp[i][j] = max(dp[i+1][j],dp[i][j-1]);
}
}
}
// 整条长度 [0,n-1]
return dp[0][n-1];
}
};