动态规划

• 代码随想录

• 解题步骤:

  • 确定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];
    }
};

---