动态规划算法

2026-09-12

引言

之前做过不少动态规划方面的题目，但是都没有系统的整理，本博文系统整理下动态规划相关的知识。 动态规划算法（Dynamic Programming，简称 DP）.它将一个问题分解为一系列更小的子问题(重叠子问题)，并通过存储子问题的解来避免重复计算，从而大幅提升时间效率。 故此，动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心算法Link，贪心没有状态推导，而是从局部直接选最优的，

动态规划问题是从底到顶，而递归算法是从顶到底。

动态规划问题的一般形式就是求最值，而求最值的核心其实就是穷举,所谓的穷举就是定义好「状态转移方程」。 但是穷举所有可行解其实并不是一件容易的事，只有列出正确的「状态转移方程」,才能正确地穷举。同时对于状态与选择的定义也是很重要的。 为此，在本博文中，解题思路都是以三步走的方式来解决问题的。

1.定义dp表(注意下标含义)，确定状态与选择。

2.确定初始状态。（边界值）。

3.确定状态转移方程，进行状态递推，自下向上(确定遍历顺序)。

PS：动态规划算法的一些手写笔记：

爬楼梯

1.自下而上，推到状态方程

首先通过经典的爬楼梯问题，导出其对应的动态规划解法

动态规划是一种“从底至顶”的方法：从最小子问题的解开始，迭代地构建更大子问题的解，直至得到原问题的解。

/* 爬楼梯：动态规划 */
int climbingStairsDP(int n) {
  if (n == 1 || n == 2)
    return n;
  // step1: 初始化dp 表，用于存储子问题的解
  vector<int> dp(n + 1);
  // step1: 确定初始状态：预设最小子问题的解
  dp[1] = 1;
  dp[2] = 2;
  // step3:确定状态转移方程，进行状态转移：从较小子问题逐步求解较大子问题
  for (int i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];//状态转移方程
  }
  return dp[n];
}

根据上面的代码，可以简单总结出动态规划问题的解题思路：

  • step1:初始化dp表。将数组𝑑𝑝称为𝑑𝑝表，𝑑𝑝[𝑖] 表示状态 𝑖 对应子问题的解。
  • step2:确定初始状态。将最小子问题对应的状态（第 1 阶和第 2 阶楼梯）称为初始状态。
  • step3:构建状态转移方程。将递推公式 𝑑𝑝[𝑖] = 𝑑𝑝[𝑖 − 1] + 𝑑𝑝[𝑖 − 2] 称为状态转移方程。

下面看看例题

时间复杂度O（N），空间复杂度为O（N）

class Solution {
  public:
      int climbStairs(int n) {
          // n个阶梯对应多少种方法(一共n+1个元素)，也就是状态dp
  
          if(n<3)//要大于等于3才适用于动态规划的问题～
              return n;
  
          // 时间复杂度O（N），空间复杂度为O（N）
  
          // step1：定义dp表
          int dp[n+1];//n个状态，对应n+1数组
  
          // step2：定义初始状态
          dp[0]=0;
          dp[1]=1;
          dp[2]=2;//一次性两级，或两次1级,故此有两种方法
  
          // step3：状态转移方程
          for(int i=3;i<n+1;i++)//注意数组是到n+1
          {
              //第n级。有n-1或n-2决定
              dp[i]=dp[i-1]+dp[i-2];//状态转移方程。
          }
  
          return dp[n];//最后返回第n阶梯的时候的解决方案
      }
  };

下面是等效的~

class Solution {
  public:
      int climbStairs(int n) {
  
          // step1:定义dp表：dp[i]=第i级时，一共的方案数
          // 状态：当前在第i阶
          // 选择：由上一阶或上两阶获取的
          int dp[n+1];
  
          // step2：初始化dp表
          dp[0]=1;
          dp[1]=1;
          
          // step3:进行状态转移
          for(int i=2;i<n+1;i++)
          {
              dp[i]=dp[i-1]+dp[i-2];
          }
  
          return dp[n];
  
      }
  };

2.最优子结构

上图仅仅是展示了动态规划的基本构建，但是一般来说，动态规划都是用来解决最优化问题的，因此进一步的，题目形如下面：

前面的动态规划的状态转移方程为：

而对于此处的最优化问题（带有代价函数的），则为：

从两个子问题最优解 𝑑𝑝[𝑖 − 1] 和 𝑑𝑝[𝑖 − 2] 中挑选出较优的那一个，并用它构建出原问题 𝑑𝑝[𝑖] 的最优解。也就是最优子结构.

因此，这个带有最优子结构的动态规划问题应该如下代码所示：

/* 爬楼梯最小代价：动态规划 */
int minCostClimbingStairsDP(vector<int> &cost) {

  int n = cost.size() - 1;

  if (n == 1 || n == 2)
    return cost[n];

  // 初始化 dp 表，用于存储子问题的解
  vector<int> dp(n + 1);

  // 初始状态：预设最小子问题的解
  dp[1] = cost[1];
  dp[2] = cost[2];

  // 状态转移：从较小子问题逐步求解较大子问题
  for (int i = 3; i <= n; i++) {
    dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
  }

  return dp[n];
}

下面看看例题

class Solution {
  public:
      int minCostClimbingStairs(vector<int>& cost) {
  
          // step1:定义dp表:dp[i]=为第i阶的时候的最小费用
          // 状态：第i阶梯（注意最后一个阶梯应该是cost.size()）
          // 选择，爬一级或两级
          int dp[cost.size()+1];

  
          // step2：初始化dp表(注意题目说的：可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。)
          dp[0]=0;//第0级的时候的费用
          dp[1]=0;//从1开始的最小为0（0和cost[0]）
  
          // step3：进行状态转移
          for(int i=2;i<cost.size()+1;i++)
          {
              dp[i]=min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);//从i-1或者i-2来的最小费用
          }

          return dp[cost.size()];

      }
  };

另外一种解法(可以理解为第一步花费，最后一步不花费，是旧版这个题目的描述)

class Solution {
  public:
      int minCostClimbingStairs(vector<int>& cost) {
  
          // step1:定义dp表:dp[i]=为从i开始走的最小费用
          // 状态：第i阶梯
          // 选择，爬一级或两级
          int dp[cost.size()];
  
          // step2：初始化dp表
          dp[0]=cost[0];//从0开始走的时候的花销
          dp[1]=cost[1];//从1开始走的时候的花销
  
          // step3：进行状态转移
          for(int i=2;i<cost.size();i++)
          {
              dp[i]=min(dp[i-1],dp[i-2])+cost[i];//当前的花销
          }
  
          //注意最后一步没有花销，因此取倒数第一或第二的最小花销
          return min(dp[cost.size()-1],dp[cost.size()-2]);
  
          //cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用
          // 第一个台阶的费用=从0开始走到1的费用
      }
  };

3.带约束导致无后效性时，需要额外添加状态来保证

若进一步的，对上面题目添加限制条件，如下：

在此新问题中，下一步选择不能仅仅由当前状态（当前所在楼梯阶数）独立决定，还和前一个状态（上一轮所在楼梯阶数）有关。 因此不满足无后效性，那么上面的状态转移方程就不适用了。 又或者说：影响当前结果的，不再是一个状态，而是两个状态（当前的阶梯数，以及上次是走1级还是2级）。

为此，扩展状态定义：状态 [𝑖, 𝑗] 表示处在第 𝑖 阶并且上一轮跳了 𝑗 阶，其中 𝑗 ∈ {1, 2} 。此状态定义有效地区分了上一轮跳了 1 阶还是 2 阶，我们可以据此判断当前状态是从何而来的。

  • 当上一轮跳了 1 阶时，上上一轮只能选择跳 2 阶，即 𝑑𝑝[𝑖, 1] 只能从 𝑑𝑝[𝑖 − 1, 2] 转移过来。
  • 当上一轮跳了 2 阶时，上上一轮可选择跳 1 阶或跳 2 阶，即 𝑑𝑝[𝑖, 2] 可以从 𝑑𝑝[𝑖−2, 1] 或 𝑑𝑝[𝑖−2, 2] 转移过来。

代码如下：

/* 带约束爬楼梯：动态规划 */
int climbingStairsConstraintDP(int n) {
  if (n == 1 || n == 2) {
  return 1;
  }
  // 初始化 dp 表，用于存储子问题的解
  vector<vector<int>> dp(n + 1, vector<int>(3, 0));
  // 初始状态：预设最小子问题的解
  dp[1][1] = 1;
  dp[1][2] = 0;
  dp[2][1] = 0;
  dp[2][2] = 1;
  // 状态转移：从较小子问题逐步求解较大子问题
  for (int i = 3; i <= n; i++) {
    dp[i][1] = dp[i - 1][2];
    dp[i][2] = dp[i - 2][1] + dp[i - 2][2];
  }
  return dp[n][1] + dp[n][2];//两者之和代表爬到第 𝑛 阶的方案总数
}

递归vs动态规划：斐波那契数列

解法1：动态规划。时间复杂度O（N），空间复杂度为O（N）

class Solution {
  public:
      int fib(int n) {
  
          //首先只有大于2才适用
          if(n<2)
              return n;
          
          //step1：定义dp表及下标的含义。
          //状态就是当前在第几个数，选择就是前面两个数的和
          int dp[n+1]; //对应于状态n
  
          // step2：状态的初始化
          dp[0]=0;
          dp[1]=1;
  
          // step3:自下而上遍历，推到状态方程
          for(int i=2;i<n+1;i++)
          {
              dp[i]=dp[i-1]+dp[i-2];//后面的每一项数字都是前面两项数字的和
          }
  
          return dp[n];
  
      }
  };

用递归的思路解题也很简单。但是这个递归调用次数类似于计算一棵二叉树的节点数，树的高度为𝑛所以总的子树数目是O（2N），对应的时间复杂度为O（2N）。空间复杂度主要由递归调用的栈空间决定。每次递归调用都会占用一定的栈空间，递归的最大深度为𝑛，因此空间复杂度为：𝑂(N)

class Solution {
  public:
      int fib(int n) {
  
          //首先只有大于2才适用
          if(n<2)
              return n;
          
          return fib(n-1)+fib(n-2);
  
      }
  };

上面递归方法如果改为带有【备忘录】的写法，时间复杂度就会降低到O（N），所谓的备忘录写法其实就是对于每个结果都先记录着，如果这个结果被计算过了，就不重新计算，直接获值。也就是说动态规划其实就是相当于带有【备忘录】的递归。只是一个是自下而上，一个是自上而下。

带有【备忘录】的递归

class Solution {
  public:
      // 带着备忘录进行递归
      int dp(vector<int> &memo, int n) {
          
          if (n == 0 || n == 1) 
              return n;//递归终止
  
          if (memo[n] != 0)  // 已经计算过，不用再计算了
              return memo[n];
              
          memo[n] = dp(memo, n - 1) + dp(memo, n - 2);
          return memo[n];
      }
      
      int fib(int n) {
  
          vector<int> memo(n+1,0);// 备忘录全初始化为 0

          // 进行带备忘录的递归
          return dp(memo, n);
  
      }    
  };

对于上面解法1的动态规划解法。进一步的把空间复杂度降为 O(1)。当前状态 n 只和之前的 n-1, n-2 两个状态有关，其实并不需要那么长的一个 DP table 来存储所有的状态

class Solution {
  public:
      int fib(int n) {
  
          //首先只有大于2才适用
          if(n<2)
              return n;
          
          //step1：定义dp表
          // int dp[n+1]; //对应于状态n
  
          // step2：状态的初始化
          // dp[0]=0;
          // dp[1]=1;
          int dp_i_2=0;
          int dp_i_1=1;
  
          // step3:自下而上，推到状态方程
          for(int i=2;i<n+1;i++)
          {
              // dp[i]=dp[i-1]+dp[i-2];//后面的每一项数字都是前面两项数字的和
              int dp_i=dp_i_1+dp_i_2;
  
              // 滚动更新
              dp_i_2=dp_i_1;
              dp_i_1=dp_i;
          }
  
          // return dp[n];
          return dp_i_1;
  
      }
  };

最大子数组和

动态规划解法。时间复杂度为O（N），空间复杂度为O（N）

class Solution {
  public:
      int maxSubArray(vector<int>& nums) {
  
         //step1：定义dp表：dp[i]=索引为i的数字,能获取的最大和
          //状态：对于索引为i的数字
          //选择：从当前索引重新开始或用之前累计的结果
          int dp[nums.size()];
  
          //step2:初始化dp表
          dp[0]= nums[0];//第一个的最大值就是第一个数
  
          // step3:进行状态转移
          int result=dp[0];//记录全部的最大值(注意，此处不能用INT_MIN,需要初始化为第一个数组)
          for(int i=1;i<nums.size();i++)
          {
              // 从当前索引从新算，或者当前+上一个状态
              dp[i]=max(nums[i],dp[i-1]+nums[i]);
              result=max(dp[i],result);
          }
  
          return result;
  
      }
  };

贪心算法的解法，当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。时间复杂度为O（N），空间复杂度为O（1）

class Solution {
  public:
      int maxSubArray(vector<int>& nums) {
  
        
          int result=INT_MIN;//注意要初始化为最小的负数，因为可能一开始就为负数
  
          int temp_sum=0;
          for(int i=0;i<nums.size();i++)
          {
             temp_sum+=nums[i];
             result=max(temp_sum,result);//每次加完后,记录最大值（最终作为全局最优）
  
              // 当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，
              // 因为负数加上下一个元素 “连续和”只会越来越小。
             if(temp_sum<0)//为负数了，马上重置
                  temp_sum=0;
              
              //注意遇到负数后，继续加和，下一个可能更大（和为正，对下一个必然是增大的作用）。
              //但是和为负数后，如果继续加下一个必然更小。
              // 为此应该选和为负的时候作为零界点
  
          }
  
          return result;
  
      }
  };

最长递增子序列

用了两个for循环，时间复杂度为O（N2）,空间复杂度为O（N）也就是存储的dp表

class Solution {
  public:
      int lengthOfLIS(vector<int>& nums) {
  
          // step1：定义dp表。状态变量应该就是n=nums.size()了吧，也是唯一的变量
          int n=nums.size();
          int dp[n];
  
          // step2：确定初始状态
          for(int i=0; i<n;i++)
          {
              dp[i]=1;//自身，长度就是1了
          }
  
          // step3:状态转移方程
          // 对于状态dp[i]。以及在i前的状态j。
          // 若nums【i】>nums【j】.那么dp【i】为dp【i】（其他值）与dp【j】+1之间的最值
          int max_len=1;
          for(int i=0;i<n;i++)
          {
              for(int j=0;j<i;j++)
              {
                  if(nums[i]>nums[j]) //注意nums只能访问到n-1
                      dp[i]=max(dp[i], dp[j]+1);//循环的其他j也参与了对比的。只是只记录最大值
              }
              max_len=max(max_len,dp[i]);//dp[i]为最大的
          }
  
          return max_len;//不能直接返回dp[n-1]，因为这是n-1位置时最大的，不是全部最大的~
      }
  };

（用vector方便初始化，且涉及到循环对比的，需要先初始化，不然就会取空的时候的地址！）

class Solution {
  public:
      int lengthOfLIS(vector<int>& nums) {
  
          //step1:定义dp表:为dp[i]=对于以 nums[i] 这个数结尾的最长递增子序列的长度
          // 故此应该是dp大小是nums.size()而不是nums.size()+1
          //状态：以 nums[i] 这个数结尾
          //选择：i之前的数进行判断
          vector<int> dp(nums.size(), 1);
          //step2:初始化dp表，为1，以 nums[i] 结尾的最长递增子序列起码要包含它自己，也就是自身长度1
  
          //step3:状态转移方程
          int max_len=0;//用于记录整个序列中最长的，因为状态对应的只是当前字符
          for(int i=0;i<nums.size();i++)
          {
              for(int j=0;j<i;j++)//由于不改变顺序，故此需要遍历的是i之前的
              {//// 寻找 nums[0..i-1] 中比 nums[i] 小的元素
                  if(nums[i]>nums[j])//对于nums[j]<nums[i]的情况，子序列的长度肯定就是dp[j]+1（但不要求连续！）
                      dp[i]=max(dp[i],dp[j]+1);//相当于把i之前的每一个都对比了～
              }
              if(dp[i]>max_len)
                  max_len=dp[i];
          }
  
          return max_len;
      }
  };

最长连续递增序列

注意要连续的

class Solution {
  public:
      int findLengthOfLCIS(vector<int>& nums) {
  
          if(nums.size()==1)//对于只有一个值的情况
              return 1;
  
          //step1:定义dp表.dp[i]对于第i个数字，递增子序列的最大长度为多少
          // 状态：当前位于第几个数字i,最大为nums.size()
          // 选择：若当前的比上一个大，那么就是之前的基础上+1
          vector<int> dp(nums.size()+1,1);
  
          // step2:初始化dp表
          // 初始化为1，自身就是1
  
          // step3:状态转移
          int max_len=0;
          for(int i=2;i<nums.size()+1;i++)
          {
              // 注意要连续的
              if(nums[i-1]>nums[i-2])//大于前一个
                  dp[i]=dp[i-1]+1;//上一个状态的值+1
              
              // 否则就是1
  
              if(dp[i]>max_len)//记录全部的最大值
                  max_len=dp[i];
          }
  
          return max_len;
      }
  };

Redraiment的走法

有点类似最长递增子序列

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin>>n;
    int temp;
    vector<int> group;
    while(cin>>temp)
    {
        group.push_back(temp);
    }

    //step1:确定dp表。dp[i]为对于第i阶，最多走多少步过来的
    int dp[n+1];

    // step2:初始化dp表：在每一轮里面初始化

    //step3:进行状态转移
    int max_step=0;
    for(int i=1;i<n+1;i++)
    {
        dp[i]=1;//每阶走了多少步都初始化为1，就是在当前阶不动，

        //由于涉及到了前面是怎么的情况，为此必须遍历i之前的对比计算
        for(int j=1;j<i;j++)//查看第j阶前面的情况
        {
            if(group[j-1]<group[i-1])//若小于i，那么就是可以从j走过来，故此+1
            {
                dp[i]=max(dp[i],dp[j]+1);
            }//反之，不能从i走到j
            else
                dp[i]=max(dp[i],1);//只能在当前格,不走
        }
        //一圈对比完后，判断最大值
        if(dp[i]>max_step)
        {
            max_step=dp[i];
        }
    }

    std::cout<<max_step;

}

合唱队：最长递增子序列与最长递减子序列的结合

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N;//N位同学
    cin>>N;

    vector<int> height_group;
    int temp;
    while(cin>>temp)
    {
        height_group.push_back(temp);
    }
    // 中间从两边递减，因此可以理解为是从左到右：最长递增子序列。从右向左：最长递减子序列

    //step1:定义dp表。第N-1个同学，最长序列为dp【N-1】
    //step2:初始化状态为第0个同学，初始化为1,也就是自身的长度
    vector<int> dp1(N,1);
    
    // 从左到右：最长递增子序列
    // step3:状态转移方程
    //对于第i个同学，对比j同学（j为0～i）
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<i;j++)
        {   
            //只要j小于i就参加对比。j大于i的就删除（不处理）
            if(height_group[i]>height_group[j])
                dp1[i]=max(dp1[i],dp1[j]+1);
        }
    }//最终获得第i个同学，最长递增子序列

    // 从右向左：最长递减子序列
    //step1:定义dp表。第N-1个同学，最长序列为dp【N-1】
    //step2:初始化状态为第0个同学，初始化为1,也就是自身的长度
    vector<int> dp2(N,1);
    
    // step3:状态转移方程
    //对于第i个同学，对比j同学（j为i～N-1），注意不考虑i的本身
    for(int i=N-1;i>=0;i--)
    {
        for(int j=N-1;j>i;j--)
        {   
            //只要j小于i就参加对比。j小于于i的就删除（不处理）
            if(height_group[j]<height_group[i])//j在i的后面，j比i小，那么就是递减
                dp2[i]=max(dp2[i],dp2[j]+1);
        }
    }//最终获得第i个同学，最长递减子序列

    //
    int maxLength = 0;
    //遍历这些同学
    for (int  i = 0; i < N; i++){
        //dp1[i]为第i个同学，从左到右的最长递增子序列
        //dp2[i] 为第i个同学，从i开始的最长递减子序列
        if (maxLength < dp1[i] + dp2[i] - 1)//i为分割点，因此需要-1
        {
            maxLength = dp1[i] + dp2[i] - 1;
            //这里的i就是划分中点
        }
    }
    std::cout << N - maxLength << endl;
    
}

二维最长递增子序列：俄罗斯套娃信封问题

此题相当于最长递增子序列的二维版本，但是需要对数组先进行排列。但是leetcode上下面代码运行会超时，只能通过85/87.时间复杂度为O（N2）,空间复杂度为O（N）

class Solution {
  public:
      static bool comparefunction(vector<int>&a, vector<int>&b)//要设置为静态成员函数
      {
          if (a[0]!=b[0])
              return a[0]<b[0];
          else
              return a[1]<b[1];
      }
      int maxEnvelopes(vector<vector<int>>& envelopes) {
          
          //注意！需要先对envelopes进行排序
          sort(envelopes.begin(),envelopes.end(),comparefunction);
  
          //step1:定义dp表：dp[i]=对于信封envelopes【i】最多的组合个数
          vector<int> dp(envelopes.size(),1);
          // step2:初始化dp表，都为1，也就是自身
  
          // step3:状态转移
          int max_len=0;
          for(int i=0;i<envelopes.size();i++)//遍历每个信封
          {
              for(int j=0;j<i;j++)//选择i的前面进行对比
              {
                  //满足要求时
                  if(envelopes[i][0]>envelopes[j][0] && envelopes[i][1]>envelopes[j][1])
                      dp[i]=max(dp[i],dp[j]+1);
              }
              if(dp[i]>max_len)
                  max_len=dp[i];
          }
  
          return max_len;
      }
  };

二分法解题将复杂度降低为O（NlogN）这个方法还不是很熟悉～

class Solution {
  public:
      static bool comparefunction(vector<int>& a, vector<int>& b) {
          if (a[0] == b[0])
              return a[1] > b[1];  // 宽度相同，高度降序排列
          return a[0] < b[0];  // 否则，宽度升序排列
      }
  
      int maxEnvelopes(vector<vector<int>>& envelopes) {
          // 对信封进行排序
          sort(envelopes.begin(), envelopes.end(), comparefunction);
  
          // 用于存储当前最长递增子序列的末尾元素
          vector<int> dp;
  
          for (auto& envelope : envelopes) {
              int height = envelope[1];
              // 使用二分查找找到第一个大于或等于当前高度的位置
              auto it = lower_bound(dp.begin(), dp.end(), height);
              if (it == dp.end()) {
                  dp.push_back(height);  // 如果没有找到，则添加到末尾
              } else {
                  *it = height;  // 如果找到了，则替换掉该位置的值
              }
          }
  
          return dp.size();  // dp的长度就是最长递增子序列的长度
      }
  };

整数拆分

某种程度上跟最长递增子序列的结构是一样的。解题的关键在于设计的状态是拆分数字i，而不是拆分为i个。只有这样才满足递推关系。其次就是对于每个数有拆与不拆两种选择

class Solution {
  public:
      int integerBreak(int n) {
  
          //step1:定义dp表：dp[i]为拆分i的时候，最大的乘积
          // 状态：拆分数字i（注意不是拆分为i个）只有这样才满足递推
          // 选择：遍历从1~j。
              // 拆分j：j*（i-j）就是目前的dp[i]
              // 不拆分j，但是拆分（i-j）那么dp[i]=j*dp[i-j]
              //因此递推方程应该是：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
  
          vector<int> dp(n+1,0);
  
          // step2:初始化dp表
          //由于n是大于等于2，因此从2开始
          dp[2]=1;
  
          if(n==2)
              return dp[2];
  
          //step3:进行状态转移
          for(int i=3;i<n+1;i++)   
          {
              // 拆分的数字,对于当前的数字i，最小为1，最大就是到数字i-1
              for(int j=1; j<i;j++)
              {
                  //拆分j：j*（i-j）
                  //不拆分j，但是拆分（i-j）那么dp[i]=j*dp[i-j]
                  //全部结果对比求最值
                  dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
              }
          }     
  
          return dp[n];
      }
  };

同时维护两个一维的dp表：摆动序列

class Solution {
  public:
      int wiggleMaxLength(vector<int>& nums) {
          
          //采用动态规划
          //step1:定义dp表
          int up[nums.size()];//从0开始，对于位置为i，最长上升摆动序列
          int down[nums.size()];//从0开始，对于位置为i，最长的下降摆动序列
  
          // step2：初始化dp表。对于只有一个元素的情况也是摆动序列
          up[0]=1;
          down[0]=1;
  
          for(int i=1;i<nums.size();i++)
          {
              if(nums[i]>nums[i-1])//当前i大于上一个值
              {
                  //删除这个值对应的i-1时最长上升摆动序列。与，i-1时最长的下降摆动序列+1成为上升序列
                  up[i]=max(up[i-1], down[i-1]+1);
                  down[i]=down[i-1];//上一个是波谷的话，当前值只能删除，为此只等于上一个状态
              }
              else if(nums[i]<nums[i-1])//当前i小于上一个值
              {
                  // 跟上面反过来
                  down[i]=max(down[i-1], up[i-1]+1);
                  up[i]=up[i-1];
              }
              else//相等的情况
              {
                  up[i] = up[i - 1];
                  down[i] = down[i - 1];
              }
  
          }
  
          return max(up[nums.size()-1],down[nums.size()-1]);//两者的最大值
  
      }
  };

此题也可以用贪心算法来解决Link

二维动态规划问题，走格子

不同路径

机器人从(0 , 0) 位置出发，到(m - 1, n - 1)终点。这点最重要！

class Solution {
  public:
      int uniquePaths(int m, int n) {
  
          //step1:定义dp表：dp[i][j]有多少条路径
          // 状态，当前位于第m行，n列，点（i,j），终点为（m-1，n-1）
          // 选择：只能向下或者向右移动一步
          int dp[m][n];
  
          //step2:初始化dp表
          dp[0][0]=1;
  
          //对于第一行
          for(int j=1;j<n;j++)
          {
              dp[0][j]=dp[0][j-1];
          }
  
          // 对于第一列
          for(int i=1;i<m;i++)
          {
              dp[i][0]=dp[i-1][0];
          }
  
          //step3:进行状态转移
          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];
  
      }
  };

走方格的方案数

如若按照上一题的思路，此题应该是有问题的，n，m的格子。终端是（n-1,m-1）

#include <iostream>
using namespace std;

int main() {
    int n,m;
    cin>>n>>m;//n为横向的格子数，m为竖向的格子数
    //注意是（0，1，2，。。。n）和（0，1，2，。。。m）一共是n+1和m+1个格子

    // step1:定义dp表，dp[i][j]:走到第i和j个格子的走法（注意是走法而不是一共走了多少格子）
    //状态：当前位于第i行第j列（注意从0开始）
    //选择：向右走或者向下走
    int dp[n+1][m+1];

    //step2:初始化dp表，为0
    dp[0][0]=0;//走法为0,不用走

    //对于第一行和第一列，只有一种走法
    for(int i=1;i<n+1;i++)
    {
        dp[i][0]=1;//从00到i0只有一种走法，就是一直往右
    }

    for(int j=1;j<m+1;j++)
    {
        dp[0][j]=1;//从00到0j只有一种走法，就是一直往下
    }

    // step3:进行状态转移
    for(int i=1;i<n+1;i++)
    {
        for(int j=1;j<m+1;j++)
        {
            dp[i][j]=dp[i-1][j]+dp[i][j-1];//只由这两种走法决定
        }
    }

    std::cout<<dp[n][m];
    
}

不同路径 II

有障碍物处不能走，因此次数为0

class Solution {
  public:
      int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
          
          int m=obstacleGrid.size();
          int n=obstacleGrid[0].size();
  
          //step1:定义dp表：dp[i][j]有多少条路径
          // 状态，当前位于第m行，n列，点（i,j），终点为（m-1，n-1）
          // 选择：只能向下或者向右移动一步
          vector<vector<int>> dp(m, vector<int>(n,0));//初始化为0，有障碍物的时候，路径数为0
  
          //step2:初始化dp表
          if(obstacleGrid[0][0]==0)//一开始就有障碍物的情况
              dp[0][0]=1;
  
          //初始化第一行
          bool flag=false;
          for(int j=1;j<n;j++)
          {
              if(obstacleGrid[0][j]==1)
              {
                  //有障碍物，那么障碍物之后的都为0
                  flag=true;
              }
              if(flag==false)
                  dp[0][j]=dp[0][j-1];
          }
  
          //初始化第一列
          flag=false;
          for(int i=1; i<m; i++)
          {
              if(obstacleGrid[i][0]==1)
              {
                  //有障碍物，那么障碍物之后的都为0
                  flag=true;
              }
              if(flag==false)
                  dp[i][0]=dp[i-1][0];
          }
  
          //step3:状态转移
          for(int i=1;i<m;i++)
          {
              for(int j=1;j<n;j++)
              {
                  if(obstacleGrid[i][j]==0)//若无障碍物，那么就是由下面两者决定
                      dp[i][j]=dp[i-1][j]+dp[i][j-1];
              }
          }
  
          return dp[m-1][n-1];
      }
  };

下降路径最小和

时间与空间复杂度都是O（N2）

class Solution {
  public:
      int minFallingPathSum(vector<vector<int>>& matrix) {
  
          //step1:定义dp表：dp【i】【j】=当前第i行与第j列时最小的路径和
          //状态：当前第i行与第j列
          //选择：由上一行的三个元素决定（三个元素最小的一个，但根据列数不一样，三个元素有条件选择）
          vector<vector<int>> dp(matrix.size(),vector<int>(matrix.size(),0));
  
          // step2:初始化dp表，实际上应该是位于当前网格的值的大小
          for(int j=0;j<matrix.size();j++)
          {
              dp[0][j]=matrix[0][j];//初始化第一行即可。（由于是从第一行的任意点开始的）
          }
  
          //step3:进行状态转移
          for(int i=1;i<matrix.size();i++)
          {
              for(int j=0;j<matrix.size();j++)//注意处理j边界的方式
              {
                  // 当前列正上方
                  int minAbove = dp[i-1][j];
  
                  if (j > 0) // 可以对比左上方元素
                      minAbove = min(minAbove, dp[i-1][j-1]);
                  
                  if (j < matrix.size() - 1) // 可以对比右上方元素
                      minAbove = min(minAbove, dp[i-1][j+1]);
                  
                  //上方三个的最小值+当前网格的值
                  dp[i][j] = matrix[i][j] + minAbove;
              }
          }
  
          //最后再统计最后一行的最小值，才可以获得总的最小值
          int min_value=INT_MAX;
          for(int j=0;j<matrix.size();j++)
          {
              if(dp[matrix.size()-1][j]<min_value)//最后一行
                  min_value=dp[matrix.size()-1][j];
          }
          return min_value;
      }
  };

最小路径和

dp表的初始化容易出错，对于第i行第j列的dp标索引应该从0开始，从1开始其实也可以只是对应处理更加复杂而已~

class Solution {
  public:
      int minPathSum(vector<vector<int>>& grid) {
  
          // step1：定义dp表，dp[i][j]表示当前位置的最小路径数值和
          // 状态：当前位于第i行第j列（注意从0开始）
          // 选择：（除了第一行和第一列外）向下或向右
          vector<vector<int>> dp(grid.size(), vector<int>(grid[0].size(),0));
          
          // step2:初始化dp表：i或j等于0的情况
          dp[0][0]=grid[0][0];
  
          // 注意！第一行和第一列仅仅有一种选择，而不是两种最小
          for(int i=1;i<grid.size();i++)
          {
              dp[i][0]=grid[i][0]+dp[i-1][0];
          }
  
          for(int j=1;j<grid[0].size();j++)
          {
              dp[0][j]=grid[0][j]+dp[0][j-1];
          }
  
  
          // step3：进行状态转移
          for(int i=1;i<grid.size();i++)
          {
              for(int j=1;j<grid[0].size();j++)
              {
                  //当前的值+(上一状态从上下来的或者从左过来的最小值)
                  dp[i][j]=grid[i][j]+min(dp[i-1][j],dp[i][j-1]);
              }
          }
  
          return dp[grid.size()-1][grid[0].size()-1];
  
      }
  };

逆向思维动态规划：地下城游戏

第一次解题的时候，想着把最小路径和改为最大路径和然后简单的对结果值进行修正希望达到最优。但实际上运行发现会选择运行28的结果。所以应该做到是损失最小，也就是负数之和最大，但是这个思路也不对，实际上就是同时考虑补充和扣减，与其如此，还不如换个思路，从右下角到左上角

class Solution {
  public:
      int calculateMinimumHP(vector<vector<int>>& dungeon) {
          // 反过来的思路，初始化血量为1，从右下角走到左上角
  
          // step1:定义dp表：dp[i][j]= 这个格子走到右下角所需要的最小生命值
          // 状态为第i行和第j列（从dungeon.size()-1与dungeon[0].size()-1开始索引）
          // 选择为： 向左 或 向上 移动一步
          vector<vector<int>> dp(dungeon.size()+1, vector<int>(dungeon[0].size()+1, INT_MAX));;
          
          // step2:初始化dp表为int的最大值（由于下面需要选择最小值），同时索引多一行一列可以避免考虑最后一列和最后一行复杂的情况
          dp[dungeon.size()][dungeon[0].size()]=1;//到最后一格之后刚好是一滴血
          dp[dungeon.size()-1][dungeon[0].size()]=1;
          dp[dungeon.size()][dungeon[0].size()-1]=1;
          
         for(int i=dungeon.size()-1;i>=0;i--)
         {
              for(int j=dungeon[0].size()-1;j>=0;j--)
              {
                  // 选择两个去向中较小的一个，也就是下一个时刻最小需要多少
                  int temp=min(dp[i+1][j],dp[i][j+1]);//可以保持从最小值从取，那么当前temp-dungeon[i][j]也是最小的情况。但是由于不能等于0，故此最小是1或者是temp-dungeon[i][j]
  
                  dp[i][j]=max(temp-dungeon[i][j],1);//要么保留1血量，要么就是当前剩余的
                  // 若dungeon[i][j]为负，那么当前应该是-dungeon[i][j]+temp，这样才可以保证能走到下一个
                  //  若dungeon[i][j]为正，那么当前只需要1就可以了，因为补充了
              }
         }
  
         return dp[0][0];
  
      }
  };

两个字符串的动态规划问题

判断子序列

编辑距离入门级题目。本质上就是只有删除这一个操作

class Solution {
  public:
      bool isSubsequence(string s, string t) {
  
          //step1：定义dp表。dp[i][j]s的第i个字符与t的第j个字符是否子序列
          // 状态：s的第i个字符与t的第j个字符（从1开始，到size()+1,这样就不用处理初始化问题）
          // 选择：等或不等，
          vector<vector<bool>> dp(s.size()+1, vector<bool>(t.size()+1, false));
  
          // step2:初始化全为false
          dp[0][0]=true;//全为空必然为子序列
          for(int j=1;j<t.size()+1;j++)
          {
              dp[0][j]=true;//s为空，那么s必然是t的子序列
          }
  
          // step3：进行状态转移
          for(int i=1;i<s.size()+1;i++)
          {
              for(int j=1;j<t.size()+1;j++)
              {
                  if(s[i-1]==t[j-1])//若两个字符相等
                      dp[i][j]=dp[i-1][j-1];//退化为上一个状态
                  else//若不等
                      dp[i][j]=dp[i][j-1];//应该删掉，再检查
              }
          }
  
          return dp[s.size()][t.size()];
      }
  };

不同的子序列

也是编辑距离类型的题目，但只有删除的操作

class Solution {
  public:
      int numDistinct(string s, string t) {
          
          //可以理解为s删掉某些字符就得到t
          //进一步的可以退化为编辑距离，
  
          //step1:定义dp表。dp[i][j]s的第i个字符与t的第j个字符的时候，s到t的方案数
          // 状态：s的第i个字符与t的第j个字符（从1开始，到size()+1,这样就不用处理初始化问题）
          // 选择：删或不删
          vector<vector<unsigned long>> dp(s.size()+1, vector<unsigned long>(t.size()+1, 0));
          // unsigned long处理极大的数组的情况
  
          //step2:初始化dp表
          dp[0][0]=1;
          for(int i=1;i<s.size()+1;i++)
          {
              dp[i][0]=1;//当t为空时，有且只有一种方案由s到t，就是s全部删掉
          }
  
          // step3：进行状态转移
          for(int i=1;i<s.size()+1;i++)
          {
              for(int j=1;j<t.size()+1;j++)
              {
                  if(s[i-1]==t[j-1])//若两个字符相等
                      dp[i][j]=dp[i-1][j-1]+dp[i-1][j];//退化为上一个状态，或者删掉s再检测（方案数为两者之和）
                  else//若不等
                      dp[i][j]=dp[i-1][j];//当前字母s删掉
              }
          }
  
          return dp[s.size()][t.size()];
  
  
      }
  };

两个字符串的删除操作

只是上面一题的进阶版，改为两个字符都可以删减了~

class Solution {
  public:
      int minDistance(string word1, string word2) {
  
          //step1:定义dp表。dp[i][j]word1的第i个字符与word2的第j个字符的时候，s到t的最小步数
          // 状态：word1的第i个字符与word2的第j个字符（从1开始，到size()+1,这样就不用处理初始化问题）
          // 选择：删或不删
          vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1, INT_MAX));
  
          //step2:初始化dp表，上面定义的时候都初始化为最大值
          dp[0][0]=0;
          // 若只有其中之一为空
          for(int i=1;i<word1.size()+1;i++)
              dp[i][0]=i;//操作数为剩余的字符数
          for(int j=1;j<word2.size()+1;j++)
              dp[0][j]=j;
  
          // step3：进行状态转移
           for(int i=1;i<word1.size()+1;i++)
              {
                  for(int j=1;j<word2.size()+1;j++)
                  {
                      if(word1[i-1]==word2[j-1])//若两个字符相等
                          dp[i][j]=dp[i-1][j-1];//退化为上一个状态，不操作，必然是最小的
                      else//若不等,两种选择之一的最小
                          dp[i][j]=min(
                              dp[i-1][j]+1,//删掉i的操作数
                              dp[i][j-1]+1//删掉j的操作数
                          );
                  }
              }
      
          return dp[word1.size()][word2.size()];
      }
  };

编辑距离

解决两个字符串的动态规划问题，一般都是用两个指针 i, j 分别指向两个字符串的最后，然后一步步往前移动，缩小问题的规模。（注意思路是往前移动，但实际上计算过程是往后移动，因为动态规划是自底向上的~）

（此题中，注释相对比较规范化了动态规划问题的解题~）时间复杂度O（MN），空间复杂度为O（MN）

class Solution {
  public:
      int minDistance(string word1, string word2) {
          // 解法：动态规划
          // 步骤1：创建动态规划的数组，dp[i][j]代表第i-1和j-1个字符的对比的情况下，最短的编辑距离～
          int dp[word1.size()+1][word2.size()+1];
  
          // 步骤1：初始化数组：当某个数组为0，另一个操作数就等于另外一个的size
          for(int i=0;i<word1.size()+1;i++)
          {
              dp[i][0]=i;
          }
          for(int j=0;j<word2.size()+1;j++)
          {
              dp[0][j]=j;
          }
  
          // 步骤二：定义状态转移方程
          for(int i=1;i<word1.size()+1;i++)
          {
              for(int j=1;j<word2.size()+1;j++)
              {
                  if(word1[i-1]==word2[j-1])//如果两个字符相等,退化为dp【i-1】【j-1】（相当于什么都不做）
                      dp[i][j]=dp[i-1][j-1];
                  else //如果不相等：
                      //增加/插入新的值：可以理解为【i+1】与【j】一样了。那么就是退化为【i】与【j-1】对比了~
                      //删除i：就相当于用i的上一个状态了【i-1】与【j】对比
                      //替换：那么就相当于只用对比前一个状态了【i-1】与【j-1】对比
                      //注意不要漏了+1（为本次操作数)
                      dp[i][j]=min(min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1])+1;
              }
          }
  
          return dp[word1.size()][word2.size()];
  
      }
  };

字符串通配符

，跟字符串编辑距离很像，只是有了其他字符因此对初始化会有影响！

#include <cctype>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    string str_1, str_2;
    cin>>str_1>>str_2;
    // 不区分大小写的匹配结果.先全部转换为小写
    // transform(str_1.begin(),str_1.end(),str_1.begin(),::tolower);
    // transform(str_2.begin(),str_2.end(),str_2.begin(),::tolower);

    // step1:创建dp表。str1中的第i个字符与第j个字符对比
    bool dp[str_1.size()+1][str_2.size()+1];

    //step2:初始化dp表，如果有一个为0，那么都不是通配
    dp[0][0]=true;
    for(int i=1;i<str_1.size()+1;i++)
    {
        if(str_1[i-1]=='*')//对于星号的情况不能全部为true，因为可能出现*A*的情况
            dp[i][0]=dp[i-1][0];
        else if(str_1[i-1]=='?')//匹配1个字符
          dp[i][0]=dp[i-1][0];
        else
            dp[i][0]=false;
    }
    //对于i=0的情况，可以通过初始化全部为false那就不用再初始化了
    for(int j=1;j<str_2.size()+1;j++)
    {
        dp[0][j]=false;
    }

    // step3:进行自下而上的状态转移，推导状态转移方程
    for(int i=1;i<str_1.size()+1;i++)
    {
        for(int j=1;j<str_2.size()+1;j++)
        {
            // if(str_1[i-1]==str_2[j-1])//若两者相同
            if(tolower(str_1[i-1])==tolower(str_2[j-1]))//若两者小写相同（忽略大小写）
            {
                dp[i][j]=dp[i-1][j-1];//那么就退化为上一个的对比
            }
            else//不等
            {
                if(str_1[i-1]=='*'
                    && 
                    (
                    (str_2[j-1]>='0' && str_2[j-1]<='9') || (str_2[j-1]>='a' && str_2[j-1]<='z')
                        ))//匹配0个或以上的字符（注：能被*和?匹配的字符仅由英文字母和数字0到9组成，下同）
                {
                  //此处也并非有*就马上为true，反推初始化也不应该出现有*就为true
                    dp[i][j]=dp[i-1][j-1] || dp[i][j-1] || dp[i-1][j];
                }
                else if(str_1[i-1]=='?'
                && 
                (
                (str_2[j-1]>='0' && str_2[j-1]<='9') || (str_2[j-1]>='a' && str_2[j-1]<='z')
                    ))//匹配1个字符
                {
                    dp[i][j]=dp[i-1][j-1];//那么就退化为上一个的对比
                }
                else
                    dp[i][j]=false;//那么就直接是false了
            }
        }
    }
    if(dp[str_1.size()][str_2.size()])
        std::cout<<"true";
    else
        std::cout<<"false";
}

回文子串

双指针法比较直接，见下题最长回文子串，此处仅用动态规划来解题

class Solution {
  public:
      int countSubstrings(string s) {
          
          // step1:定义dp表：dp[j][i]=起点为j终点为i的字符它是否为回文子串
          // 状态：起点为j终点为i的字符(i从0开始，到s.size()-1)
          vector<vector<bool>> dp(s.size(),vector<bool>(s.size(),false));
  
          // step2:初始化dp表，初始化为false
  
          //step3:进行状态转移
          int result=0;//总的回文子串数目
          for(int i=0;i<s.size();i++)//注意遍历的顺序，i为终点
          {
              for(int j=0;j<=i;j++)//j为从0~i
              {
                  if(i==j)//自身必然是回文子串
                  {
                      dp[j][i]=true;
                      result++;
                  }
                  else if(j+1==i)//偶数的情况
                  {
                      dp[j][i]=(s[i]==s[j]);
                      if(dp[j][i]==true)//若是回文子串
                          result++;
                  }
                  else //i与j相差大于1
                  {
                      dp[j][i]= (s[i]==s[j]) && dp[j+1][i-1];//从小范围到大范围
                      if(dp[j][i]==true)//若是回文子串
                          result++;
                  }
  
              }
          }
  
          return result;
      }
  };

以i为起点，j为终点（这个思路更好理解~）

class Solution {
  public:
      int countSubstrings(string s) {
          
          // step1:定义dp表：dp[i][j]=起点为i终点为j的字符它是否为回文子串
          // 状态：起点为i终点为j的字符(i从0开始，到s.size()-1)
          vector<vector<bool>> dp(s.size(),vector<bool>(s.size(),false));
  
          // step2:初始化dp表，初始化为false
  
          //step3:进行状态转移
          int result=0;//总的回文子串数目
          for(int i=s.size()-1;i>=0;i--)//注意遍历的顺序，i为起点，从后往前遍历
          {
              for(int j=i;j<s.size();j++)//j为终点
              {
                  if(i==j)//自身必然是回文子串
                  {
                      dp[i][j]=true;
                      result++;
                  }
                  else if(i+1==j)//偶数的情况
                  {
                      dp[i][j]=(s[i]==s[j]);
                      if(dp[i][j]==true)//若是回文子串
                          result++;
                  }
                  else //i与j相差大于1
                  {
                      dp[i][j]= (s[i]==s[j]) && dp[i+1][j-1];//从小范围到大范围
                      if(dp[i][j]==true)//若是回文子串
                          result++;
                  }
  
              }
          }
  
          return result;
      }
  };

最长回文子串

动态规划解法，时间复杂度与空间复杂度都是O（N^2）。对于此类形的题目，定义的dp表应该为dp[j][i]：j代表了起点，i代表了终点。对比是否回文子串的过程就是dp[j][i]=(i++j && dp[j+1][i-1]).同时注意奇数与偶数的情况（aba与aa都是回文子串）

#include <iostream>
#include <vector>
using namespace std;

int main() {
    //本质上就是求最长的回文子串。可以采用动态规划或者双指针法

    string input_str, result_str;
    getline(cin,input_str);

    //step1:定义dp表，对于起点为j终点为i的dp[j][i]是否为回文串
    // i，j为字符的索引
    //step2:初始化dp表：全部为false
    vector< vector <bool> > dp(input_str.size(), vector<bool> (input_str.size(),false));

    int max_len=0;
    // step3:状态转移方程
    for(int i=0;i<input_str.size();i++)
    {
        for(int j=0;j<=i;j++)
        {
            if(i==j)//自身必然为回文子串。//对应aba的情况，基数位
                dp[j][i]=true;//注意是j～i
            else if(i==j+1)//对应偶数位，回文子串
            {
                dp[j][i]=(input_str[i]==input_str[j]);
            }
            else//其他情况
                dp[j][i]= (input_str[i]==input_str[j]) && dp[j+1][i-1];//从小范围到大范围

            if(dp[j][i]==true)//若当前为回文子串
            {
                if(i-j+1>max_len)
                    max_len=i-j+1;//如果是回文子串且长度大于记录值,则更新
            }
        }
    }

    std::cout<<max_len<<std::endl;
}

也可以采用双指针解法。时间复杂度是O（N^2）更上面一样的。但空间复杂度更小，为O（1）

#include <iostream>
using namespace std;

// 对于以left与right为中心的最长回文子串
// 通过左右指针向两边扩散
string function(string s, int left, int right)
{
    //确保不越界以及相等
    while(left>=0 && right<s.size() &&s[left]==s[right])
    {
        left--;
        right++;
    }
    //若不等的话，会跳出来。所以应该是当前的left+1到right为目标结果
    return s.substr(left+1,right-(left+1));
}

int main() {
    //本质上就是求最长的回文子串。可以采用动态规划或者双指针法

    string input_str, result_str;
    getline(cin,input_str);

    for(int i=0;i<input_str.size();i++)
    {
        //以i为中心的，奇数字符串
        string s1=function(input_str,i,i);
        //以i为中心的，偶数字符串
        string s2=function(input_str,i,i+1);

        // 保存最长的
        result_str= result_str.size()>s1.size()? result_str:s1;
        result_str= result_str.size()>s2.size()? result_str:s2;
    }

    std::cout<<result_str.size();
}

最长回文子序列

以i为起点，j为终点

class Solution {
  public:
      int longestPalindromeSubseq(string s) {
  
       // step1:定义dp表：dp[i][j]=字符串s在[i, j]范围内，最长的回文子序列长度
      // 状态：起点为i终点为j的字符(i从0开始，到s.size()-1)
      vector<vector<int>> dp(s.size(),vector<int>(s.size(),0));
  
      // step2:初始化dp表，自身必然是回文子串
      for(int i=0;i<s.size();i++)
          dp[i][i]=1;
  
      //step3:进行状态转移
      for(int i=s.size()-1;i>=0;i--)//注意遍历的顺序，i为起点
      {
          for(int j=i+1;j<s.size();j++)//j为终点(j=i的情况上面考虑了)
          {
              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];//i为起点，j为终点。
      }
  };

公共子串计算

最简单直接了当的方法应该是从最长的序列开始递减计算

#include <iostream>
using namespace std;

int main() {
    string str_1, str_2;
    cin>>str_1>>str_2;

    if(str_1.size()>str_2.size())
        swap(str_1,str_2);//确保1为最短

    for(size_t len=str_1.size();len>=0;len--)
    {
        for(int i=0;i<=str_1.size()-len;i++)
        {
            string temp=str_1.substr(i,len);
            if(str_2.find(temp)!=string::npos)//找到了
            {
                std::cout<<temp.size();
                return 0;
            }
        }
    }
    std::cout<<"-1";
}

这里也给出动态规划的解法

#include <iostream>
using namespace std;

int main() {
    string str_1, str_2;
    cin>>str_1>>str_2;

    //step1:定义dp表。dp【i】【j】为对比第i与j个字符，为公共子串的长度
    int dp[str_1.size()+1][str_2.size()+1];

    // step2:初始化状态
    dp[0][0]=0;
    for(int i=1;i<str_1.size()+1;i++)
        dp[i][0]=0;
    for(int j=1;j<str_2.size()+1;j++)
        dp[0][j]=0;

    int max_len=0;//多加个记录会简单很多～
    //进行状态转移
    for(int i=1;i<str_1.size()+1;i++)
    {
        for(int j=1;j<str_2.size()+1;j++)
        {
            if(str_1[i-1]==str_2[j-1])//相等
            {
                dp[i][j]=dp[i-1][j-1]+1;//长度+1
            }
            else {
                dp[i][j]=0;//不等，那么最长的公共子串长度为0
            }
            if(dp[i][j]>max_len)
                max_len=dp[i][j];
        }
    }

    std::cout<<max_len;
}

最长重复子数组

跟最长公共子串是一样的解题思路~

class Solution {
  public:
      int findLength(vector<int>& nums1, vector<int>& nums2) {
  
          // 相当于两个字符串的最长公共子串
  
          // step1:定义dp表。dp[i][j],对于nums1中第i个数字与nums2中第j个数字，最长的公共子串的数
          // 状态：nums1中第i个数字与nums2中第j个数字(从1开始，对应选取的为nums1[i-1]和nums2[j-1])
          //而这样定义就不需要考虑初始化的问题了，否则如果以0开始，那么初始化就要检查nums1[0]和nums2[0]是否相等
          vector<vector<int>> dp(nums1.size()+1, vector<int>(nums2.size()+1,0));
  
          // step2:初始化dp表
          // 上面已经全部初始化为0了~
  
          //step3：进行状态转移
          int max_len=0;//用于记录最长的长度
          for(int i=1;i<nums1.size()+1;i++)
          {
              for(int j=1;j<nums2.size()+1;j++)
              {
                  if(nums1[i-1]==nums2[j-1])
                      dp[i][j]=max(dp[i][j], dp[i-1][j-1]+1);//记录最长的
                  else//两者不相等
                      dp[i][j]=0;
  
                  if(dp[i][j]>max_len)
                      max_len=dp[i][j];
              }
          }
  
          return max_len;
  
      }
  };

最长公共子序列

注意要的是子序列，不是子串。不要求连续的了，只是需要有相对顺序

class Solution {
  public:
      int longestCommonSubsequence(string text1, string text2) {
  
          // step1:定义dp表。dp[i][j]=对于text1中的第i个字母，text2中的第j个字母，他们所对应的公共子序列最大长度
          // 状态：对于text1中的第i个字母，text2中的第j个字母（j从1开始。size()+1）
          // 选择：两个相等就+1，。不等就清0~
          vector<vector<int>> dp(text1.size()+1, vector<int>(text2.size()+1,0));
  
          // step2:初始化dp表，都初始化为0了，注意i从1开始，所以不用考虑第一个的情况
  
          //step3:进行状态转移
          int max_len=0;//记录最长的字符
  
          for(int i=1;i<text1.size()+1;i++)
          {
              for(int j=1; j<text2.size()+1;j++)
              {
                  if(text1[i-1]==text2[j-1])//若相等
                      dp[i][j]=dp[i-1][j-1]+1;
                  else//不等
                      dp[i][j]=max(dp[i][j-1],dp[i-1][j]);//若不等，但最大应该还是删除这个后的最大值
  
                  // 注意dp[i][j]已经一直更新记录全部的最大子序列长度，因此无需额外记录
  
                  // // 记录全部的最大值
                  // if(dp[i][j]>max_len)
                  //     max_len=dp[i][j];
              }
          }
  
          // return max_len;
          return dp[text1.size()][text2.size()];
      }
  };

不相交的线

直线不能相交，这就是说明在字符串A中 找到一个与字符串B相同的子序列，且这个子序列不能改变相对顺序，只要相对顺序不改变，链接相同数字的直线就不会相交。（本质上跟上一题“最长公共子序列”是一模一样的）

class Solution {
  public:
      int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
  
          //step1:定义dp表.dp[i][j]=对于nums1的第i个数字与nums2的第j个数字对应的最大连线数
          // 状态:对于nums1的第i个数字与nums2的第j个数字
          //选择:连线或不连线
          vector<vector<int>> dp(nums1.size()+1, vector<int>(nums2.size()+1,0));
  
          // step2:初始化dp表,上面都初始化为0了
  
          // step3:进行状态转移
          for(int i=1;i<nums1.size()+1;i++)
          {
              for(int j=1;j<nums2.size()+1;j++)
              {
                  if(nums1[i-1]==nums2[j-1])//相等,那么就可以选择连或不连
                      // dp[i][j]=max(
                      //     dp[i-1][j-1]+1, //连了
                      //     max(dp[i-1][j],dp[i][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[nums1.size()][nums2.size()];
  
      }
  };

背包问题

背包问题有以下分类：

实际主要的应该是0-1背包问题与完全背包问题。他们之间的区别是：0-1背包问题是每个物品只能用一次，而完全背包问题是每个物品可以用无数次。

0-1背包问题

题目：给你一个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。其中第 i 个物品的重量为 wt[i]，价值为 val[i]。现在让你用这个背包装物品，每个物品只能用一次，在不超过被包容量的前提下，最多能装的价值是多少？

首先要明确两点，「状态」和「选择」。

  • 对于状态，如何才能描述一个问题局面？只要给几个物品和一个背包的容量限制，就形成了一个背包问题呀。所以状态有两个，就是「背包的容量」和「可选择的物品」。因此需要用二维数组。

  • 对于选择，选择就是「装进背包」或者「不装进背包」。只有两种。

确定了状态与选择，那么基本主体的框架就出来了：

for 状态1 in 状态1的所有取值：
  for 状态2 in 状态2的所有取值：
      for ...
          dp[状态1][状态2][...] = 择优(选择1，选择2...)

第一步需要明确dp数组的定义。 上述状态定义为两个，一个二维的dp数组，dp[i][w] 的定义如下：对于前 i 个物品，当前背包的容量为 w，这种情况下可以装的最大价值是 dp[i][w]。

第二步需要确定初始的状态。那么就是dp[0][..] = dp[..][0] = 0，因为没有物品或者背包没有空间的时候，能装的最大价值就是 0。

第三步就是确定状态转移方程（其实也就是上面「首先」的时候完成的了）

  • dp[i][w] 表示：对于前 i 个物品（从 1 开始计数），当前背包的容量为 w 时，这种情况下可以装下的最大价值是 dp[i][w]

  • 如果没有把这第 i 个物品装入背包，那么很显然，最大价值 dp[i][w] 应该等于 dp[i-1][w]，继承之前的结果。

  • 如果把这第 i 个物品装入了背包，那么 dp[i][w] 应该等于 val[i-1] + dp[i-1][w - wt[i-1]]。

⚠️由于数组索引从 0 开始，而定义中的 i 是从 1 开始计数的，所以 val[i-1] 和 wt[i-1] 表示第 i 个物品的价值和重量。

int knapsack(int W, int N, vector<int>& wt, vector<int>& val) {
  assert(N == wt.size());

  //step1:初始化dp表
  vector<vector<int>> dp(N + 1, vector<int>(W + 1));

  //step2:初始化状态（其实也就是上面初始化为0，为此不用操作）
  dp[0][..] = 0
  dp[..][0] = 0
  
  //step3:进行状态转移
  for (int i = 1; i <= N; i++) {
    for (int w = 1; w <= W; w++) {
        //注意是否有这种剪枝的情况
        if (w - wt[i - 1] < 0) {
            // 这种情况下只能选择不装入背包
            dp[i][w] = dp[i - 1][w];
        } else {
            // 装入或者不装入背包，择优
            dp[i][w] = max(
                dp[i - 1][w - wt[i-1]] + val[i-1], //把物品 i 装进背包
                dp[i - 1][w] //不把物品 i 装进背包
            );
        }
    }
}
  return dp[N][W]

背包问题变体之子集分割/子集背包问题/分割等和子集

用递归的思路去解题不是不行，数组多了就会超出时间限制，当然也可以用回溯算法中的“划分为k个相等的子集”（还没尝试）

class Solution {
  public:
      bool callback(vector<int>& nums, int sum1, int smu2, int index)
      {
          // 递归终止条件
          if(index==nums.size())
              return sum1==smu2;
  
          return callback(nums,sum1+nums[index], smu2, index+1) || callback(nums,sum1, smu2+nums[index], index+1); 
      }
  
      bool canPartition(vector<int>& nums) {
  
          return callback(nums,0,0,0);
      }
  };

采用动态规划.一个商品如果可以重复多次放入是完全背包，而只能放入一次是01背包.而本题是每个元素只能用一次，因此属于01背包问题

class Solution {
  public:
      bool canPartition(vector<int>& nums) {
          
          int sum=0;
          for(auto num:nums)
              sum+=num;
          
          if(sum%2!=0)//若不能被2整除，那就直接false
              return false;// 和为奇数时，不可能划分成两个和相等的集合
          
          int target=sum/2;//也就是背包的体积
  
          //step1: 定义dp表：dp【i】【j】=对于第i个物品，当前和值为j，若为true就是刚好分完，若为false就是还没分完
          // 状态：第i个数（集合内的元素/商品），j为当前存放的值和（相当于价值）
          // 选择：第i个数选择放与不放
         bool dp[nums.size()+1][target+1];
  
         //step2:初始化状态方程
          // j==0相当于装满了，可以理解为true了，正好分配成功了   
         for(int i=0;i<nums.size()+1;i++)
         {
              dp[i][0]=true;
         }
  
         //i==0，那就是没有数据，但是j！=0那么就是没分完，但是没得分了，所以为false
         for(int j=1;j<target+1;j++)
         {
              dp[0][j]=false;
         }
  
          //step3:进行状态转移
          for(int i=1;i<nums.size()+1;i++)
          {
              for(int j=1;j<target+1;j++)
              {
                  //当前目标值小于数组上的数字，那么就不能取
                  if(j<nums[i-1])//那么就是当前数字不取，那么就是跟上一个状态一样
                      dp[i][j]=dp[i-1][j];
                  else
                  {
                      //取或者不取这个数字只要有一个为true都是true
                      dp[i][j]= dp[i-1][j-nums[i-1]] || dp[i-1][j];
                  }
              }
          }
  
          return dp[nums.size()][target];
      }
  };

最后一块石头的重量II

跟分割等和子集非常像，只是前者是判断是否均分，此处是判断最多放了一半多少（那么总的减去一半*2就是剩余的）

此外，注意sum需要初始化为0,对于涉及到遍历，特别是循环调用而不是单纯赋值的，一般都需要初始化，此外，可通过debug模式一步一步输出value查看bug

class Solution {
  public:
      int lastStoneWeightII(vector<int>& stones) {
  
          //尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小
          //其次每个石头只能选一次，因此是01背包问题，
          //跟分割等和子集非常像，只是前者是判断是否均分，此处是判断最多放了一半多少（那么总的减去一半*2就是剩余的）
  
          int sum=0, target=0;//注意sum要初始化为01
          for(auto stone:stones)
              sum+=stone;
          target=sum/2;
  
          //step1:定义dp表：dp[i][j]=当前最大的容量
          // 状态：当前第i个石头，剩余背包容量为j
          // 选择：放或不放当前的石头
          vector< vector<int>> dp(stones.size()+1, vector<int>(target+1, 0));
  
          //step2：初始化dp表都为0
  
          // step3：进行状态转移
          for(int i=1;i<stones.size()+1;i++)
          {
              for(int j=1;j<target+1;j++)
              {   
                  // 不选当前物品i,那么最大容量就退化为dp[i-1][j]
                  //选当前物品i，那么最大容量就是dp[i-1][j-stones[i-1]]+stones[i-1]（当前物品）
                  if(j<stones[i-1])//当前是不能选的
                  {
                      dp[i][j]=dp[i-1][j];
                  }
                  else
                      dp[i][j]=max(dp[i-1][j],dp[i-1][j-stones[i-1]]+stones[i-1]);//不选或者选的最大值
              }
          }
  
          return sum-dp[stones.size()][target]*2;
      }
  };

目标和

看到这道题的第一思路就是采用回溯算法，跟组合和有点类似。注意终止条件应该是index==nums.size()而不是index==nums.size()-1

class Solution {
  public:
      void backtrack(vector<int>& nums, int each_path, int& results, int target, int index)
      {
          //递归终止条件
          if(index==nums.size())//超越了~
          {
              if(each_path==target)
                  results++;
              
              return;
          }
  
          //做选择
          each_path+=nums[index];
          backtrack(nums,each_path,results,target,index+1);//下一个
          //撤销选择
          each_path-=nums[index];
  
          //做选择
          each_path-=nums[index];//减法
          backtrack(nums,each_path,results,target,index+1);//下一个
          //撤销选择
          each_path+=nums[index];//加回来
  
      }
  
      int findTargetSumWays(vector<int>& nums, int target) {
  
          int each_path=0;
          int results=0;
          backtrack(nums,each_path,results,target,0);
  
          return results;
      }
  };

当然，用动态规划去解题也是可以的。但是对于j为什么要从0开始理解得不是很透彻，且比回溯算法的思路复杂多了~

（PS：由于目标值会存在0，因此应该从0开始）

class Solution {
  public:
      int findTargetSumWays(vector<int>& nums, int target) {
  
          //也可以看成是01背包问题。背包的容量为target，对每个物品，nums进行加或减的处理
          // 假设加法的总和为x，那么减法对应的总和就是sum - x。
          // 那么就有x - (sum - x) = target。故此x = (target + sum) / 2
          // 此时问题就转化为，用nums装满容量为x的背包，有几种方法。
  
          int sum=0;
          for(auto num:nums)
          {
              sum+=num;
          }
  
          // 不能被2整除，此时没有方案
          if ((target + sum) % 2 !=0) 
              return 0; 
  
          //如果target 的绝对值已经大于sum，那么也是没有方案的。
          if (abs(target) > sum)
              return 0; 
  
          target=(target+sum)/2;
  
          //step1:定义dp表。dp[i][j]=对于物品i当前能填满背包容量j的方法数
          // 状态：物品i以及当前的容量j
          // 选择：加或不加入背包
          vector< vector<int>> dp(nums.size()+1, vector<int>(target+1, 0));
  
          // step2:初始化dp表，对于背包容量为0的情况，不选物品就可以填满，因此方案数为1
          for(int i=0;i<nums.size()+1;i++)
          {
              dp[i][0]=1;
          }
  
          // step3：进行状态转移
          for(int i=1;i<nums.size()+1;i++)
          {
              // for(int j=1;j<target+1;j++)
              for(int j=0;j<target+1;j++)//注意 j 从 0 开始，这样可以正确处理所有可能的背包容量。
              {
                  if(j<nums[i-1])//当前物品不能选
                      dp[i][j]=dp[i-1][j];
                  else//方案分别为选当前物品和不选当前物品的方案数总和
                      dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i-1]];
  
              }
          }
          return dp[nums.size()][target];
  
      }
  };

三维动态规划之一和零

关键在于分析问题进行数学建模

class Solution {
  public:
      int findMaxForm(vector<string>& strs, int m, int n) {
          
          //对于strs 数组里的元素就是物品，每个物品都是一个，因此属于0、1背包问题
          // 而背包为二维的，分别的容量是m和n（每个物品的重量若有0或有1都会占用m和n）
          //至于价值则是字符数目（每个物品的价值为1）
  
          //step1：定义dp表:dp[i][j][k]=对于第i个物品，当前容量为j和k时，最大的字符数目
          // 状态：当前第i个物品，对应两个背包的容量分别为m和n
          //选择，当前物体放或不放
          vector<vector<vector<int>>> dp(strs.size()+1, vector<vector<int>>(m+1, vector<int> (n+1, 0)));
  
          //step2:初始化dp表
          // 当j与k都为0的时候，就是不能再放了，因此最长的字符数为0
          // 当i为0，就是物体为0，那么最长的字符数也是0
  
          //step3：进行状态转移
          for(int i=1;i<strs.size()+1;i++)
          {
              //对于当前物品，先统计它的0和1的数目
              int oneNum = 0, zeroNum = 0;
              auto temp_str=strs[i-1];//当前的字符
              for(char c: temp_str)
              {
                  if(c=='0')
                      zeroNum++;//0的数目自加
                  else
                      oneNum++;//1的数目自加
              }
  
              for(int j=0;j<m+1;j++)//剩余装0的容量
              {
                  for(int k=0;k<n+1;k++)//剩余装1的容量
                  {
                      if(zeroNum>j || oneNum>k)//当前的01的数目大于容量就不能放
                          dp[i][j][k]=dp[i-1][j][k];
                      else
                      {
                          // 可以选择放或不放
                          dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-zeroNum][k-oneNum]+1);//多了一个，同时要减去容量
                      }
                  }
              }
          }
  
          return dp[strs.size()][m][n];
      }
  };

完全背包问题

所谓的完全背包问题是指：有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。 完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。

01背包和完全背包唯一不同就是体现在遍历顺序上：

  • 如果求组合数就是外层for循环遍历物品，内层for遍历背包。

  • 如果求排列数就是外层for遍历背包，内层for循环遍历物品。

零钱兑换

如果用基本的动态规划问题的思路去解题。此处引出动态规划问题中状态以及选择量的确定过程：

1、确定「状态」，也就是原问题和子问题中会变化的变量。 由于硬币数量无限，硬币的面额也是题目给定的，只有目标金额会不断地向 base case （凑够了目标金额，为0）靠近，所以唯一的「状态」就是目标金额 amount。

2、确定「选择」，也就是导致「状态」产生变化的行为。 目标金额为什么变化呢，因为你在选择硬币，你每选择一枚硬币，就相当于减少了目标金额。所以说所有硬币的面值，就是的「选择」。

3、明确 dp 数组的定义。 即题目要求的凑出目标金额所需的「最少硬币数量」，所以是最少的金币数量。

此题的难点就是用什么作为状态，如何确定dp表。

class Solution {
  public:
      int coinChange(vector<int>& coins, int amount) {
  
          if(coins.size()==0)
              return -1;
  
          // // step!:确定状态，建立dp表。唯一可能的状态就是amount了
          // int dp[amount+1];//状态amount时,需要的最小的硬币的数量
          // // 注意初始化为amount + 1 ，因为凑成 amount 金额的硬币数最多只可能等于 amount（全用 1 元面值的硬币）
          // // 所以初始化为 amount + 1 就相当于初始化为正无穷
          vector<int> dp(amount + 1, amount + 1);//这个写法正确且简单
  
          // step2：确立初始状态
          dp[0]=0;
          // for(int i=1;i<amount+1;i++)
          // {
          //     dp[i]=amount+1;
          // }
  
          // step3: 确定状态转移方程
          for(int n=0; n<amount+1; n++)
          {
              for(int each_coin:coins)
              {
                  // 减去当前的面值小于0，那么当前面值不适用,跳过使用下一个试试
                  if(n-each_coin<0)
                  {
                      continue;
                  }
                  else//若当前面值可以用
                  {
                      //当前n的最小值由当前n(不选硬币)
                      // 以及
                      // 当前面值选择这个硬币，那么就是n减去each_coin的组成
                    dp[n]=min(dp[n],1+dp[n-each_coin]);
                  }
  
              }
          }
          return (dp[amount]==amount+1)? -1: dp[amount];
      }
  };

下面可能更好理解

class Solution {
  public:
      int coinChange(vector<int>& coins, int amount) {
          
          // step1:定义dp表，代表对于需要的金额i，dp【i】状态为[最少的硬币个数]
          vector<int> dp(amount+1, 0);//当目标金额为 i 时，至少需要 dp[i] 枚硬币凑出
  
          // step2:确定初始状态，当总金额为0的时候，最小的硬币数量为0
          dp[0]=0;
  
          // step3：进行状态转移
          for(int i=1;i<amount+1;i++)//遍历所有状态的所有取值
          {
              //由于每轮是要选最值的，故此必须先初始化！
              dp[i]=amount+1;//每一轮对其进行初始化，初始化为每个面值为1元的硬币+1，那么就是最大的。也是全部的最大
              for(auto each_coin:coins)//选择对应的面值
              {
                  if(i-each_coin<0)//剪枝，当前硬币面值太大了
                      continue;
                  else
                      dp[i]=min(dp[i],dp[i-each_coin]+1);//不选这个面值，或者选这个面值，两种情况的最小
              }
          }
  
          if(dp[amount]==amount+1)//没有面值合适,故此没有发生变化～
              return -1;
          else
              return dp[amount];
      }
  };

但实际上也是一个完全背包问题。 两道题可以相互转换，“物品”对应“硬币”、“物品重量”对应“硬币面值”、“背包容量”对应“目标金额”。 优化目标相反，完全背包问题是要最大化物品价值，零钱兑换问题是要最小化硬币数量。 完全背包问题是求“不超过”背包容量下的解，零钱兑换是求“恰好”凑到目标金额的解。

下面看看完全背包问题的解法

class Solution {
  public:
      int coinChange(vector<int>& coins, int amount) {
          
          int n = coins.size();
          int MAX = amount + 1;//最大的硬币数目

          //step1: 定义 dp 表：dp[i][j]=前种硬币能够凑出金额的最少硬币数量
          // 状态：i中物品，当前的金额数
          // 选择：用或者不用当前面值的硬币
          vector<vector<int>> dp(n + 1, vector<int>(amount + 1, 0));

          // step2:初始化状态：对于硬币数为0，但是需要的金额数不为0的情况，凑不到了为此质为0
          for (int a = 1; a <amount+1; a++) {
              dp[0][a] = MAX;//当前没有硬币了，为此是最大的
          }

          //对于其他情况，比如需要金额为0，那么最小的金币数也是0，已经初始化了~

          //  step3，进行状态转移
          for (int i = 1; i <n+1; i++) {
              for (int a = 1; a <amount+1; a++) {
                  if (coins[i - 1] > a) {
                      // 若超过目标金额，则不选硬币 i
                      dp[i][a] = dp[i - 1][a];
                  } else {
                      // 不选和选硬币 i 这两种方案的较小值
                      dp[i][a] = min(
                          dp[i - 1][a], //不选择
                          dp[i][a - coins[i - 1]] + 1);//选择的最小值
                  }
              }
          }
          return dp[n][amount] != MAX ? dp[n][amount] : -1;
          }
  };

零钱兑换 II

，题目跟上面很类似的，但此处不是求最优子问题，求解是总共有多少数目可以填满，可以转换为背包问题

此处有一个细节点，是先遍历物体在遍历背包的容量（跟下面的组合总和 Ⅳ相反）

对于大部分的完全背包的两个for循环的先后顺序都是可以的。因为纯完全背包求得装满背包的最大价值是多少，和凑成总和的元素有没有顺序没关系，即：有顺序也行，没有顺序也行！

而本题要求凑成总和的组合数，元素之间明确要求没有顺序。 所以纯完全背包是能凑成总和就行，不用管怎么凑的。 假设：coins[0] = 1，coins[1] = 5。 那么就是先把1加入计算，然后再把5加入计算，得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。 但是如果把遍历背包容量放外面，背包容量的每一个值，都是经过 1 和 5 的计算，包含了{1, 5} 和 {5, 1}两种情况。此时算出来的其实就是排列数了！

class Solution {
  public:
      int change(int amount, vector<int>& coins) {
  
          //step1: 定义dp表：dp[i][j]为第i个硬币,当前的金额数为j,有多少种方法可以放满
          // 若只使用 coins 中的前 i 个（i 从 1 开始计数）硬币的面值，若想凑出金额 j，有 dp[i][j] 种凑法。
          // 状态：第i个硬币，现在的金额数
          // 选择：用或不用当前的硬币
          int dp[coins.size()+1][amount+1];
  
          // step2:初始化状态（base case最重要）
          for(int i=0;i<coins.size()+1;i++)
          {
              dp[i][0]=1;//对于目标金额为0，什么都不做就是一种做法，直接可以凑出
          }
  
          for(int j=1;j<amount+1;j++)
          {
              dp[0][j]=0;//没有金币了，但是面值不为0，那么肯定凑不出，就为0
          }
  
          // step3:进行状态转移
          for(int i=1;i<coins.size()+1;i++)
          {
              for(int j=1;j<amount+1;j++)
              {
                  if(j<coins[i-1])//那么就是不能选当前的硬币
                      dp[i][j]=dp[i-1][j];
                  else
                  {
                      //不放以及放，各一种做法，结果应该为两者之和.但是对于放了，你还可以从i个中选，因为金币的数量是无限的！
                      dp[i][j]=dp[i-1][j]+dp[i][j-coins[i-1]];
                  }
              }
          }
          
          return dp[coins.size()][amount];
  
      }
  };

当然也可以不用背包问题的思路去解题！但是思路相对有点绕~

class Solution {
  public:
      int change(int amount, vector<int>& coins) {
  
          //不用背包问题的思路去解决~
  
          // step1:定义dp表：dp[i]=当前金额为i时，总的硬币组合方案
          // 状态：当前的金额，i，需要为amount+1
          //选择：用或不用第i个金币（有条件，必须要满足当前金额i大于这个金币的数值）
          vector<int> dp (amount+1,0);
  
          //step2：初始化dp
          dp[0]=1;//当金额为0的时候，方案数为1
          // 其余情况均初始化为0，组合方案为0（注意涉及到循环运算的时候需要预先给值）
  
          //step3 进行状态转移
          //每种金币都可以选
          for(auto each_coin:coins)
          {
              //首先对于这个面值的金币，i至少等于each_coin
              for(int i=each_coin;i<amount+1;i++)
              {
                  //故此，当前状态的数目等于上一次使用这个面值的金币在加一次这个面值
                  dp[i]+=dp[i-each_coin];
                  // 而由于统计一共的方法数目，因此需要把其他时候的也加入。这就意味着必须初始化dp[i]=0
              }
  
          }
  
          return dp[amount];
  
      }
  };

组合总和 Ⅳ

第一个思路也是用回溯算法去解此题（相当于无重可复选的情况），但由于是排列情况，计算时间非常大，会导致超时

class Solution {
  public:
      void backtrack(vector<int>& nums, int target,int each_path, int& results)
      {
          if(each_path==target)//找到目标
          {
              results++;
              return;
          }
  
          for(int i=0;i<nums.size();i++)
          {
              //若加了会超过阈值就剪枝
              if(nums[i]>target-each_path)
                  continue;
              
              //前序位置做选择
              each_path+=nums[i];
  
              //递归
              backtrack(nums, target,each_path,results);
  
              //后序位置撤销选择
              each_path-=nums[i];
          }
      }
  
      int combinationSum4(vector<int>& nums, int target) {
  
          int results=0;
          int each_path=0;
          //无重可复选
          backtrack(nums, target,each_path,results);
          return results;
      }
  };

采用动态规划解题，注意也不能用《零钱兑换 II》中的解法1（背包问题）的思路去解题，因为顺序不一样，算不同的组合数！

如果把遍历nums（物品）放在外循环，遍历target的作为内循环的话，举一个例子：计算dp[4]的时候，结果集只有 {1,3} 这样的集合，不会有{3,1}这样的集合，因为nums遍历放在外层，3只能出现在1后面！ 所以本题遍历顺序最终遍历顺序：target（背包）放在外循环，将nums（物品）放在内循环，内循环从前到后遍历。

class Solution {
  public:
      int combinationSum4(vector<int>& nums, int target) {
  
          // 完全背包问题
          
          //step1：定义dp表：dp[i][j]=对于当前第i个物体，剩余总数为j的时候的排列组合个数
          // 状态：当前第i个物体，剩余总数为j 
          // 选择：选或不选这个物体，且物体可以多次选择
          vector<vector<int>> dp(nums.size() + 1, vector<int>(target + 1, 0));
  
          //step2:初始化dp表
          //当物体数为0的时候为0（上面已经初始化了）
          for(int i=0;i<nums.size() + 1;i++)
          {
              dp[i][0]=1;//对于目标金额为0，什么都不做就是一种做法，直接可以凑出
          }
  
          //step3:进行状态转移（为了得到的是排列数，因此先遍历容量，再到物体）
          for(int j=0;j<target+1;j++)//遍历金额
          {
              for(int i=1;i<nums.size() + 1;i++)//遍历物体
              {
                  if(j<nums[i-1] //相当于当前不能选
                  || dp[i-1][j] > INT32_MAX-dp[nums.size()][j-nums[i-1]]  //测试用例有两个数相加超过int的数据,因此超过就默认不选
                  )
                      dp[i][j]=dp[i-1][j];
                  else
                      // dp[i][j]=dp[i-1][j]+dp[i][j-nums[i-1]];//不选和选各一种方案（这是错的，对应出来只是组合数）
                      dp[i][j]=dp[i-1][j]+dp[nums.size()][j-nums[i-1]];//不选和选各一种方案
                      // 而对于选，应该是从nums.size()中选的，而不是单纯的i
                      
              }
          }
          return dp[nums.size()][target];
      }
  };

用一维数组也可以解决，但是如果是int的话可能越界，因此用long形

class Solution {
  public:
      int combinationSum4(vector<int>& nums, int target) {
  
          // 完全背包问题
          
          //step1：定义dp表：dp[i]目标金额为i的时候全部的排列数
          // 状态：剩余金额总数为i 
          // 选择：选或不选这个物体，且物体可以多次选择，注意是全排列
          // vector<int> dp(target + 1, 0);
          vector<unsigned long> dp(target + 1, 0);
  
          //step2:初始化dp表
          //当物体数为0的时候为0
          dp[0]=1;//对于目标金额为0，什么都不做就是一种做法，直接可以凑出
  
          //step3:进行状态转移
          for(int i=1;i<target+1;i++)// 遍历背包
          {
              //遍历每个数字(物体)
              for(int num:nums)
              {
                  if(i>=num)//当前数字可以加入
                      dp[i]+=dp[i-num];//组合数统计
              }
          }
          return dp[target];
      }
  };

完全平方数

class Solution {
  public:
      int numSquares(int n) {
  
          //对于和为n，可以理解为从1~n个数，每个数i^2作为可以选的物体，
          // 且物体（数）可以被选择多次，也就是完全背包问题
          // 进一步地，可选的i^2必然是小于等同于n的
  
          int range=sqrt(n);//向下取整
  
          //step1：定义dp表：dp[i][j]=对于物体i，容量为j，最少的数量
          // 状态，物体i，背包的容量为n
          // 选择，物体i选或不选。对应的重量为i^2；范围为1~range
          vector<vector<int>> dp(range+1, vector<int>(n+1,INT_MAX));//由于取最小值，因此统一初始化为最大值
  
          // step2:初始化dp表
          //当1=1的时候，数值应该是正好等于容量值的
          for(int j=1;j<n+1;j++)
          {
              dp[1][j]=j;//j个1
          }
  
          //当j=1时，数值应该就是都是1的
          for(int i=1;i<range+1;i++)
          {
              dp[i][1]=1*1;
          }
  
          //当j=0的时候，可以选的数量为0（注意题目说了从1开始的）
          for(int i=1;i<range+1;i++)
          {
              dp[i][0]=0;
          }
  
          // step3：进行状态转移（先物品，后背包，因此为组合数）
          for(int i=2;i<range+1;i++)//遍历物品
          {
              for(int j=1;j<n+1;j++)//遍历背包
              {
                  if(j-i*i<0)//不能选当前值
                      dp[i][j]=dp[i-1][j];
                  else
                      dp[i][j]=min(
                          dp[i][j], min(
                              dp[i-1][j],//不选当前值
                              dp[i][j-i*i]+1//选了当前值，那么当前值还可以再选,注意，选了数目需要+1
                          )
                      );
              }
          }
  
          return dp[range][n];
      }
  };

单词拆分

跟顺序有关，故此必然是先遍历背包，再遍历物体

同时注意是dp[wordDict.size()][j-wordDict[i-1].size()]而不是dp[i][j-wordDict[i-1].size()]，因为是从所有的单词中找，而不是当前的单词中找

class Solution {
  public:
      bool wordBreak(string s, vector<string>& wordDict) {
  
          //意味着可以选多次，因此属于多重背包问题
  
          //step1：定义dp表。dp[i][j]=对于第i个物品，当前字符串所以为j的时候，是否拼接
          // 状态：选择物品i，j当前到第几个单词(字符串为背包容量)
          // 选择：当前物品/单词，选或不选
          vector<vector<bool>> dp(wordDict.size()+1, vector<bool>(s.size()+1,false));
  
          // step2:初始化dp表
          // 对于j=0，也就是目标字符串为0的时候，肯定是可以拼接的（什么都不做）
          for(int i=0;i<wordDict.size()+1;i++)
          {
              dp[i][0]=true;
          }
  
          //step3:进行状态转移（由于本题跟顺序有关，故此必然是先遍历背包，再遍历物体）
          for(int j=1;j<s.size()+1;j++)//遍历背包容量
          {
              for(int i=1;i<wordDict.size()+1;i++)//遍历物体
              {
                  if(j<wordDict[i-1].size())//也就是剩余容量的尺寸小于当前单词的尺寸，当前物品不能用
                      dp[i][j]=dp[i-1][j];
                  else
                  {
                      //查看在0~j这个位置上，是否能找到wordDict[i-1]
                      // string sub_str=s.substr(0,j);//先截取当前的字符串（当前背包的容量）
                      // if(sub_str.find(wordDict[i-1])!=string::npos)//找到了，但是不一定是末尾的字符
                      string sub_str = s.substr(j - wordDict[i-1].size(), wordDict[i-1].size());
                      if(sub_str==wordDict[i-1])//要严格是最后一个
                      {//当前字符用或不用中有true即为true
                           dp[i][j]=dp[i-1][j] //不用当前单词
                                  || dp[wordDict.size()][j-wordDict[i-1].size()];//用了当前单词，还可以继续从所有单词中找（但是用了剩余容量要减去长度）
  
                      }//若找不到，就是当前字符不能用，那么就等于上一状态的
                      else
                          dp[i][j]=dp[i-1][j];
                  }
              }
          }
  
          return dp[wordDict.size()][s.size()];
  
      }
  };

多重背包

有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。

这就是典型的多重背包问题，但是本质上还是01背包问题，只是在01背包问题的基础上，每个物品的数量不再是1个，而是有多个。每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了。

分组背包问题：购物单

这道题其实就是在01背包问题的基础上，添加了各种约束。使得整体比较复杂。解题的关键点是：

1、每次只处理主件。如果是附件的话，状态等于上一次。

2、所谓的状态分为：不买、买主件、买主件+1个附件、买主件+2个附件。只有四个状态。而不买跟当前是附件的状态一样，都是继承上一个状态

3、在讨论买主件、主件+1附件、主件+2附件的时候，是依次递推满足的情况下再记录状态，不然会超时。

#include <iostream>
#include <utility>  // 包含 pair 和 make_pair 的定义
#include <vector>   // 包含 vector 的定义
using namespace std;

int main() {
    int N, m;

    cin >> N; //总的钱的数目
    cin >> m; //可购买物品的个数

    // int v, p, q;
    // v 表示该物品的价格， p 表示该物品的重要度（ 1 ~ 5 ）， q 表示该物品是主件还是附件。如果 q=0 ，表示该物品为主件，如果 q>0 ，表示该物品为附件，
    // vector< pair<int, pair<int, int>> > all_item(m+1);//要m+1个，因为下面的索引也是从1开始的
    // for (int i = 1; i < m+1; ++i) {
    //     cin >> v >> p >> q;
    //     all_item[i] = make_pair(v, make_pair(p, q));//保证了索引从1开始。因为下面也是从1开始的
    // }
    //all_item的size为m
    vector<int> v(m + 1), p(m + 1), q(m + 1);
    for (int i = 1; i <= m; ++i) {
        cin >> v[i] >> p[i] >> q[i];
    }

    //由于是求解最优子问题，采用动态规划
    // step1: 定义dp表,购买第m个物体时，此时预算为N的时候的最大满意度
    //状态：当前第i个物品，当前的预算为j
    //选择：对于当前的物品，买与不买：如果是附件，不买。如果是主件，则分为买主件、买主件+1个附件、买主件+2个附件
    vector< vector<int>> dp(m + 1, vector<int> (N + 1, 0));
    //step2:初始化状态，当当前物品不买的时候，初始化为0

    //step3:进行自下而上的状态转移方程
    for (int i = 1; i < m + 1; i++) {//从第一个物品开始一个一个看
        //for (int j = N; j >= 0; j--) //预算从N开始算。没花钱（也可以~）
        for (int j = 0; j <N+1; j++) 
        {
            // 先继承上一个状态（由于下面计算中涉及到了各种情况的最值对比）
            dp[i][j] = dp[i - 1][j];//其实也就是不买的情况

            //只考虑主件，非主件时不处理，相当于只继承之前的状态
            if (q[i] == 0) {
                // 当前的状态为买了主件后的贡献量+上一个状态的贡献量
                // vs
                // 不买当前主件。上一状态的贡献量
                if (j >= v[i]) 
                { //若可以买
                    //买与不买之间的最大值。注意，当前如果买了，那么上一个状态可以花的额度就只有j - temp_v
                    dp[i][j] = max(dp[i - 1][j - v[i]] + v[i] * p[i]
                                    , dp[i - 1][j]);
                    //考虑主件+第一个1个附件
                    for (int k = 1; k < m + 1; k++) { //遍历all_item
                        if (q[k] == i && j >= v[i] + v[k]) 
                        { //当前主件的第一个附件
                            dp[i][j] = max(dp[i - 1][j - v[i] - v[k]]
                                            + v[i] * p[i]
                                            + v[k] * p[k]
                                            , dp[i][j]);//注意对比的为当前的

                            int k1=k;//下面考虑买两个物品（寻找当前主件的第二个附件）
                            for (int k2 = k1 + 1; k2 < m + 1; k2++) {
                                if (
                                    q[k2] == i
                                    && j >= v[i] + v[k1] + v[k2]) 
                                { //当前主件的第二个附件
                                    dp[i][j] = max(dp[i - 1][j - v[i] - v[k1] - v[k2]] +
                                                v[i] * p[i]
                                                + v[k1] * p[k1]
                                                + v[k2] * p[k2]
                                                , dp[i][j]);//注意对比的为当前的
                                }
                            }
                        }
                    }

                    // //考虑主件+2个附件
                    // for (int k1 = 1; k1 < m + 1; k1++) { //遍历all_item
                    //     for (int k2 = k1 + 1; k2 < m + 1; k2++) {
                    //         if (q[k1] == i
                    //                 && q[k2] == i
                    //                 && j >= v[i] + v[k1] + v[k2]) { //当前主件的附件
                    //             dp[i][j] = max(dp[i - 1][j - v[i] - v[k1] - v[k2]] +
                    //                            v[i] * p[i]
                    //                            + v[k1] * p[k1]
                    //                            + v[k2] * p[k2]
                    //                            , dp[i][j]);//注意对比的为当前的
                    //         }
                    //     }
                    // }
                }

            }

        }
    }
    std::cout << dp[m][N];
}

打家劫舍系列问题

打家劫舍

class Solution {
  public:
      int rob(vector<int>& nums) {
  
          //当前屋偷与不偷由前一个房屋和前两个房屋是否被偷
  
          // step1：定义dp组。dp[i]，位于房屋i的时候最高的金额数
          // 状态：当前第i个房屋
          // 选择，该房屋偷或不偷
          vector<int> dp(nums.size()+1, 0);
  
          //step2:初始化dp组
          // 0的时候没有偷，故此初始化了为0
          dp[1]=nums[0];//1的时候，偷了金额数肯定是最大的
  
          //step3：进行状态转移
          for(int i=2;i<nums.size()+1;i++)
          {
              dp[i]=max(
                  dp[i-1],//前一个偷了，当前不能偷
                  dp[i-2]+nums[i-1]//前一个没偷，那么就是dp[i-2]+当前偷了获取的价值
              );            
          }
  
          return dp[nums.size()];
      }
  };

另一种解法：两个一维数组的动态规划

class Solution {
  public:
      int rob(vector<int>& nums) {
  
          //当前屋偷与不偷由前一个房屋和前两个房屋是否被偷
  
          // step1：定义dp组。dp[i]，位于房屋i的时候最高的金额数
          // 状态：当前第i个房屋
          // 选择，该房屋偷或不偷
          // dp[i][0];//当前不偷
          // dp[i][1];//当前偷
          vector<vector<int>> dp(nums.size()+1, vector<int>(2,0));
  
          //step2:初始化dp组
          dp[1][0]=0;//1的时候，不偷，那么金额数为0
          dp[1][1]=nums[0];//1的时候偷了，那么金额数为nums[0]
  
          //step3：进行状态转移
          for(int i=2;i<nums.size()+1;i++)
          {
              // dp[i][0]=dp[i-1][1];//当前不偷，那么必然是因为上一个时刻偷了
              dp[i][0] = max(dp[i-1][0], dp[i-1][1]);  // 当前不偷，那么上一个时刻可以偷了，也可以没偷，二者最大值！
              dp[i][1]=dp[i-1][0]+nums[i-1];//当前偷了，那么必然是上一个时刻没偷,同时加上当前时刻的价值
          }
  
          return max( dp[nums.size()][0] , dp[nums.size()][1] );
      }
  };

打家劫舍II

class Solution {
  public:
  
      int robrange(vector<int>& nums, int start, int end) {//原本可以理解为start=0； end为nums.size()
          
          //当前屋偷与不偷由前一个房屋和前两个房屋是否被偷
  
          // step1：定义dp组。dp[i]，位于房屋i的时候最高的金额数
          // 状态：当前第i个房屋
          // 选择，该房屋偷或不偷
          vector<int> dp(end+1, 0);
  
          //step2:初始化dp组
          // 0的时候没有偷，故此初始化了为0
          dp[start+1]=nums[start];//1的时候，偷了金额数肯定是最大的
  
          //step3：进行状态转移
          for(int i=start+2;i<end+1;i++)
          {
              dp[i]=max(
                  dp[i-1],//前一个偷了，当前不能偷
                  dp[i-2]+nums[i-1]//前一个没偷，那么就是dp[i-2]+当前偷了获取的价值
              );            
          }
  
          return dp[end];
      }
  
  
      int rob(vector<int>& nums) {
  
          if (nums.size() == 1) 
              return nums[0];//对于size数目为1的话，下面result1会报错
          
          //由于是成环的，因此首元素和尾元素不能同时偷
          int result1=robrange(nums, 0, nums.size()-1);//考虑首元素，不考虑尾元素
          int result2=robrange(nums, 1, nums.size());//不考虑首元素，考虑尾元素
  
          return max(result1, result2);
      }
  };

打家劫舍 III

本题其实是在上面两题的基础上把数据结构改成了树的形式

对于树的话，首先就要想到遍历方式，前中后序（深度优先搜索）还是层序遍历（广度优先搜索）。详细请见博客Link

注意 vector<int>{0,0} 或 vector<int> a(2,0) 都是两个0的vector，

 /**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    //dp表：0为当前节点无被偷，1为当前节点被偷
    vector<int> traverse(TreeNode* root)
    {
        if(root==nullptr)//到达根节点
            return vector<int>{0,0};//注意为中括号！！！

        vector<int> left_result=traverse(root->left);
        vector<int> right_result=traverse(root->right);

        // 后序位置
        //当前偷了，那么左与右必然都没有被偷,两者的最大值+当前偷的结果
        int cur_result_1=left_result[0]+right_result[0]+root->val;

        //当前没有偷，那么应该是：可以偷也可以不偷左右节点，则取较大的情况
        int cur_result_0=max(left_result[0],left_result[1])
                        +max(right_result[0],right_result[1]);

        return vector<int>{cur_result_0,cur_result_1};//注意为中括号！！！
    }

    int rob(TreeNode* root) {
        vector<int> result = traverse(root);
        return max(result[0],result[1]);//根节点偷与不偷
        // 由于每个节点只有偷与不偷两种状态，因此从末端到顶端，遍历统计根节点不偷与偷的情况
    }
};

（三维动态规划/两个二维动态规划）买卖股票的最佳时机系列问题

这部分主要参考：一个方法团灭 LeetCode 股票买卖问题，不过原文确实写得比较差，此处给出本人总结的思路.

k次交易

class Solution {
  public:
      int maxProfit(int k, vector<int>& prices) {//注意k是买k次
  
          //step1:确定dp表：dp[i][j]=当前在第i天，还有j次交易的情况下，最大的利润（加上0或1表示是否持有股票）
          // 状态：在第i天（i从0开始），当前允许的最大交易次数k，当前的持有状态（1 表示持有，0 表示没有持有）
          //选择，买入、卖出、无操作。但都是有条件的
              // 1、卖必须在买之后
              // 2、买也必须在卖之后
              // 3、无操作也分为买之后或卖之后
              // 4、买需要k>0
          vector<vector<vector<int>>> dp(prices.size(), vector<vector<int>>(k+1, vector<int>(2, 0)));
  
          //step2:初始化dp
          //处理操作数为0的情况（不能买入）
          for(int i=0;i<prices.size();i++)
          {
              dp[i][0][0]=0;//交易次数为0了，没持有，那么利润就是0
              dp[i][0][1]=INT_MIN;//不允许交易的情况下，是不可能持有股票的。得先买才可持有
          }
  
          //对于第0天的时候，dp[0][...][0]=0;还没开始且不持有，为此利润必然是0
          for(int j=1;j<k+1;j++)
          {
              dp[0][j][0]=0;//利润为0
              dp[0][j][1]=dp[0][j-1][0]-prices[0];// 第0天，要持有股票，利润只有可能为 -prices[0],当前需要买入，为此操作数-1。
          }
          
  
          //step3:
          for(int i=1;i<prices.size();i++)
          {
              for(int j=1;j<k+1;j++)
              {
                  //当前不持有股票的最大值
                  dp[i][j][0]=max(dp[i-1][j][0],//当前不操作，就是继续不持股票，那么操作数没变，天数i-1 
                                  //当前选择卖掉股票，那么结果就是不持有。但是上一天必然是持有且没有买操作数不变
                                  dp[i-1][j][1]+prices[i]);//卖掉今天价格，钱变多
                  //当前持有股票的最大值
                  dp[i][j][1]=max(dp[i-1][j][1],//当前不操作，就是继续持股票，那么操作数没变，天数i-1 
                                  //当前选择买股票，那么结果就是持有。但是上一天必然是没持有，且买了，操作数-1
                                  dp[i-1][j-1][0]-prices[i]);//买入今天价格，钱变少                        
              }
          }
  
          //即最后一天，最多允许 K 次交易，最多获得多少利润。
          return dp[prices.size()-1][k][0];//注意最后的股票卖出必然比还没卖出去的利润更大
      }
  };

一次交易

此题相当于，只进行一次交易，相当于题目188中的 k = 1

class Solution {
  public:
      int maxProfit(vector<int>& prices) {
          int k=1;//初始化为1次交易
          //step1:确定dp表：dp[i][j]=当前在第i天，还有j次交易的情况下，最大的利润（加上0或1表示是否持有股票）
          // 状态：在第i天（i从0开始），当前允许的最大交易次数k，当前的持有状态（1 表示持有，0 表示没有持有）
          //选择，买入、卖出、无操作。但都是有条件的
              // 1、卖必须在买之后
              // 2、买也必须在卖之后
              // 3、无操作也分为买之后或卖之后
              // 4、买需要k>0
          vector<vector<vector<int>>> dp(prices.size(), vector<vector<int>>(k+1, vector<int>(2, 0)));
  
          //step2:初始化dp
          //处理操作数为0的情况（不能买入）
          for(int i=0;i<prices.size();i++)
          {
              dp[i][0][0]=0;//交易次数为0了，没持有，那么利润就是0
              dp[i][0][1]=INT_MIN;//不允许交易的情况下，是不可能持有股票的。得先买才可持有
          }
  
          //对于第0天的时候，dp[0][...][0]=0;还没开始且不持有，为此利润必然是0
          for(int j=1;j<k+1;j++)
          {
              dp[0][j][0]=0;//利润为0
              dp[0][j][1]=dp[0][j-1][0]-prices[0];// 第0天，要持有股票，利润只有可能为 -prices[0],当前需要买入，为此操作数-1。
          }
          
  
          //step3:
          for(int i=1;i<prices.size();i++)
          {
              for(int j=1;j<k+1;j++)
              {
                  //当前不持有股票的最大值
                  dp[i][j][0]=max(dp[i-1][j][0],//当前不操作，就是继续不持股票，那么操作数没变，天数i-1 
                                  //当前选择卖掉股票，那么结果就是不持有。但是上一天必然是持有且没有买操作数不变
                                  dp[i-1][j][1]+prices[i]);//卖掉今天价格，钱变多
                  //当前持有股票的最大值
                  dp[i][j][1]=max(dp[i-1][j][1],//当前不操作，就是继续持股票，那么操作数没变，天数i-1 
                                  //当前选择买股票，那么结果就是持有。但是上一天必然是没持有，且买了，操作数-1
                                  dp[i-1][j-1][0]-prices[i]);//买入今天价格，钱变少                        
              }
          }
  
          //即最后一天，最多允许 K 次交易，最多获得多少利润。
          return dp[prices.size()-1][k][0];//注意最后的股票卖出必然比还没卖出去的利润更大
      }
  };

化简代码的写法

class Solution {
  public:
      int maxProfit(vector<int>& prices) {
          //step1:确定dp表：dp[i][j]=当前在第i天，还有j次交易的情况下，最大的利润（加上0或1表示是否持有股票）
          // 状态：在第i天（i从0开始），当前的持有状态（1 表示持有，0 表示没有持有）
          //选择，买入、卖出、无操作。但都是有条件的
              // 1、卖必须在买之后
              // 2、买也必须在卖之后
              // 3、无操作也分为买之后或卖之后
          vector<vector<int>> dp(prices.size(), vector<int>(2, 0));
  
          //step2:初始化dp
          //对于第0天的时候，dp[0][0]=0;还没开始且不持有，为此利润必然是0
          dp[0][0]=0;//利润为0
          dp[0][1]=-prices[0];// 第0天，要持有股票，利润只有可能为 -prices[0],当前需要买入。
          
          //step3:
          for(int i=1;i<prices.size();i++)
          {
              //当前不持有股票的最大值
              dp[i][0]=max(dp[i-1][0],//当前不操作，就是继续不持股票，天数i-1 
                              //当前选择卖掉股票，那么结果就是不持有。但是上一天必然是持有
                              dp[i-1][1]+prices[i]);//卖掉今天价格，钱变多
              //当前持有股票的最大值
              dp[i][1]=max(dp[i-1][1],//当前不操作，就是继续持股票，天数i-1 
                              //当前选择买股票，那么结果就是持有。但是上一天必然是没持有
                              -prices[i]);//买入今天价格，钱变少     
                              //注意，此处不为dp[i-1][0]-prices[i]，因为k=0时，为0！！！    
                              //且如果时在当天买入的，那么之前就是没持有，那么确实是-prices[i]
          }
  
          //即最后一天，最多允许 K 次交易，最多获得多少利润。
          return dp[prices.size()-1][0];//注意最后的股票卖出必然比还没卖出去的利润更大
      }
  };

无限次交易

此题相当于题目188中的无限次交易。注意此处跟121题的区别其实只是当前持有时dp[i][1]，如果当前时买了，是否应该考虑之前的状态！只有一次交易则不用考虑，因为之前肯定不持有股票（必然没钱），但是如果时无限次交易则必须要考虑之前不持有股票的情况了（有可能已经有利润）。

class Solution {
  public:
      int maxProfit(vector<int>& prices) {
          //step1:确定dp表：dp[i][j]=当前在第i天，还有j次交易的情况下，最大的利润（加上0或1表示是否持有股票）
          // 状态：在第i天（i从0开始），当前的持有状态（1 表示持有，0 表示没有持有）
          //选择，买入、卖出、无操作。但都是有条件的
              // 1、卖必须在买之后
              // 2、买也必须在卖之后
              // 3、无操作也分为买之后或卖之后
          vector<vector<int>> dp(prices.size(), vector<int>(2, 0));
  
          //step2:初始化dp
          //对于第0天的时候，dp[0][0]=0;还没开始且不持有，为此利润必然是0
          dp[0][0]=0;//利润为0
          dp[0][1]=-prices[0];// 第0天，要持有股票，利润只有可能为 -prices[0],当前需要买入。
          
          //step3:
          for(int i=1;i<prices.size();i++)
          {
              //当前不持有股票的最大值
              dp[i][0]=max(dp[i-1][0],//当前不操作，就是继续不持股票，天数i-1 
                              //当前选择卖掉股票，那么结果就是不持有。但是上一天必然是持有
                              dp[i-1][1]+prices[i]);//卖掉今天价格，钱变多
              //当前持有股票的最大值
              dp[i][1]=max(dp[i-1][1],//当前不操作，就是继续持股票，天数i-1 
                              //当前选择买股票，那么结果就是持有。但是上一天必然是没持有
                              dp[i-1][0]-prices[i]);//买入今天价格，钱变少，对应要考虑上一次不持有     
          }
  
          //即最后一天，最多允许 K 次交易，最多获得多少利润。
          return dp[prices.size()-1][0];//注意最后的股票卖出必然比还没卖出去的利润更大
      }
  };

无限次交易+冷冻期

关键只是冷冻期就必须考虑当前持有可以是上次不持有然后当前买入。但是上次不持有就只能是上次的上次本来就不持有，而不能是上次卖出导致不持有，因为有冷冻期。因此需要针对i-2的情况额外初始化dp表

class Solution {
  public:
      int maxProfit(vector<int>& prices) {
          //step1:确定dp表：dp[i][j]=当前在第i天，还有j次交易的情况下，最大的利润（加上0或1表示是否持有股票）
          // 状态：在第i天（i从0开始），当前的持有状态（1 表示持有，0 表示没有持有）
          //选择，买入、卖出、无操作。但都是有条件的
              // 1、卖必须在买之后
              // 2、买也必须在卖之后
              // 3、无操作也分为买之后或卖之后
          vector<vector<int>> dp(prices.size(), vector<int>(2, 0));
  
          //step2:初始化dp
          //对于第0天的时候，dp[0][0]=0;还没开始且不持有，为此利润必然是0
          dp[0][0]=0;//利润为0
          dp[0][1]=-prices[0];// 第0天，要持有股票，利润只有可能为 -prices[0],当前需要买入。

          //对于第一天（由于下面i-2，必须从第2天开始，为此此处需要额外递推一次）
          if(prices.size()>1)//注意只有一个输入的情况
         {
           dp[1][0]=max(dp[0][0],//当前不操作，就是继续不持股票，天数i-1 
                              //当前选择卖掉股票，那么结果就是不持有。但是上一天必然是持有
                              dp[0][1]+prices[1]);//卖掉今天价格，钱变多
           dp[1][1]=max(dp[0][1],//当前不操作，就是继续持股票，天数i-1 
                              //当前选择买股票，那么结果就是持有。但是上一天必然是没持有
                              dp[0][0]-prices[1]);//买入今天价格，钱变少，对应要考虑上一次不持有(中不操作)的情况 
         }
          
          //step3:进行状态转移
          for(int i=2;i<prices.size();i++)//要考虑从第二天开始
          {
              //当前不持有股票的最大值
              dp[i][0]=max(dp[i-1][0],//当前不操作，就是继续不持股票，天数i-1 
                              //当前选择卖掉股票，那么结果就是不持有。但是上一天必然是持有
                              dp[i-1][1]+prices[i]);//卖掉今天价格，钱变多
              //当前持有股票的最大值
              dp[i][1]=max(dp[i-1][1],//当前不操作，就是继续持股票，天数i-1 
                              //当前选择买股票，那么结果就是持有。但是上一天必然是没持有
                              dp[(i-1)-1][0]-prices[i]);//买入今天价格，钱变少，对应要考虑上一次不持有(中不操作)的情况   
                              //但是上次不持有，必须是上次没有卖掉。所以必然为上次不操作的情况dp[(i-1)-1][0] 
          }
  
          //即最后一天，最多允许 K 次交易，最多获得多少利润。
          return dp[prices.size()-1][0];//注意最后的股票卖出必然比还没卖出去的利润更大
      }
  };

无限次交易+手续费

只是在上一刻持有并当前需要卖出的时候，考虑手续费即可

class Solution {
  public:
      int maxProfit(vector<int>& prices, int fee) {
          //step1:确定dp表：dp[i][j]=当前在第i天，还有j次交易的情况下，最大的利润（加上0或1表示是否持有股票）
          // 状态：在第i天（i从0开始），当前的持有状态（1 表示持有，0 表示没有持有）
          //选择，买入、卖出、无操作。但都是有条件的
              // 1、卖必须在买之后
              // 2、买也必须在卖之后
              // 3、无操作也分为买之后或卖之后
          vector<vector<int>> dp(prices.size(), vector<int>(2, 0));
  
          //step2:初始化dp
          //对于第0天的时候，dp[0][0]=0;还没开始且不持有，为此利润必然是0
          dp[0][0]=0;//利润为0
          dp[0][1]=-prices[0];// 第0天，要持有股票，利润只有可能为 -prices[0],当前需要买入。
          
          //step3:
          for(int i=1;i<prices.size();i++)
          {
              //当前不持有股票的最大值
              dp[i][0]=max(dp[i-1][0],//当前不操作，就是继续不持股票，天数i-1 
                              //当前选择卖掉股票，那么结果就是不持有。但是上一天必然是持有
                              dp[i-1][1]+prices[i]-fee);//卖掉今天价格，钱变多，但额外多了手续费
              //当前持有股票的最大值
              dp[i][1]=max(dp[i-1][1],//当前不操作，就是继续持股票，天数i-1 
                              //当前选择买股票，那么结果就是持有。但是上一天必然是没持有
                              dp[i-1][0]-prices[i]);//买入今天价格，钱变少，对应要考虑上一次不持有     
          }
  
          //即最后一天，最多允许 K 次交易，最多获得多少利润。
          return dp[prices.size()-1][0];//注意最后的股票卖出必然比还没卖出去的利润更大
      }
  };

只进行2次交易，k=2

只是188题目中k=2的特例而已。当然此题也有简化版本，其实也就是把k的情况给列出来，不用维护数组而已，但是本人觉得还是应该按K次来计算，不然重新维护，更乱！

class Solution {
  public:
      int maxProfit(vector<int>& prices) {
  
          int k=2;
          //step1:确定dp表：dp[i][j]=当前在第i天，还有j次交易的情况下，最大的利润（加上0或1表示是否持有股票）
          // 状态：在第i天（i从0开始），当前允许的最大交易次数k，当前的持有状态（1 表示持有，0 表示没有持有）
          //选择，买入、卖出、无操作。但都是有条件的
              // 1、卖必须在买之后
              // 2、买也必须在卖之后
              // 3、无操作也分为买之后或卖之后
              // 4、买需要k>0
          vector<vector<vector<int>>> dp(prices.size(), vector<vector<int>>(k+1, vector<int>(2, 0)));
  
          //step2:初始化dp
          //处理操作数为0的情况（不能买入）
          for(int i=0;i<prices.size();i++)
          {
              dp[i][0][0]=0;//交易次数为0了，没持有，那么利润就是0
              dp[i][0][1]=INT_MIN;//不允许交易的情况下，是不可能持有股票的。得先买才可持有
          }
  
          //对于第0天的时候，dp[0][...][0]=0;还没开始且不持有，为此利润必然是0
          for(int j=1;j<k+1;j++)
          {
              dp[0][j][0]=0;//利润为0
              dp[0][j][1]=dp[0][j-1][0]-prices[0];// 第0天，要持有股票，利润只有可能为 -prices[0],当前需要买入，为此操作数-1。
          }
          
  
          //step3:
          for(int i=1;i<prices.size();i++)
          {
              for(int j=1;j<k+1;j++)
              {
                  //当前不持有股票的最大值
                  dp[i][j][0]=max(dp[i-1][j][0],//当前不操作，就是继续不持股票，那么操作数没变，天数i-1 
                                  //当前选择卖掉股票，那么结果就是不持有。但是上一天必然是持有且没有买操作数不变
                                  dp[i-1][j][1]+prices[i]);//卖掉今天价格，钱变多
                  //当前持有股票的最大值
                  dp[i][j][1]=max(dp[i-1][j][1],//当前不操作，就是继续持股票，那么操作数没变，天数i-1 
                                  //当前选择买股票，那么结果就是持有。但是上一天必然是没持有，且买了，操作数-1
                                  dp[i-1][j-1][0]-prices[i]);//买入今天价格，钱变少                        
              }
          }
  
          //即最后一天，最多允许 K 次交易，最多获得多少利润。
          return dp[prices.size()-1][k][0];//注意最后的股票卖出必然比还没卖出去的利润更大
  
      }
  };

参考资料