- 1基于SSM+Jsp+Mysql的医院预约挂号系统
- 2使用LSTM和GAN预测亚马逊股票价格的时空序列模型
- 36000字长文，带你用Python完成 “Excel合并(拆分)” 的各种操作！_python excel拆分与合并
- 4电源设计的BUCK-BOOST电路_buck-boost csdn
- 5iphone计算机显示过程,如何将视频从iPhone传输到计算机（PC和Mac）
- 6Python 下载 图片、音乐、视频(requests、you-get、pycurl、wget、ffmpeg)_python request 下载图片
- 7大模型和数据要素赋能智慧环保大数据平台解决方案_环保领域的数据资源目录系统的数据指标有哪些
- 8mysql连接池的设计与实现
- 9导致程序员写出烂代码的35个恶习，看看你染上了几个？
- 10ue4 运行禁用鼠标_[UE4] VS code使用LuaPanda断点调试
动态规划C++详解（知识点与LeetCode题目解析）_动态规划求解斐波那契数列vector容器定义dp
赞
踩
目录
一、动态规划概念
动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解
其主要用于解决动规基础、背包问题、打家劫舍、股票问题和子序列问题。
二、动态规划运用规范
在运用动态规划的时候，通常需要按下面的步骤去思考规划
1.首先确定dp数组以及下标的含义 --> 这就是确定问题的可行解集合
2.确定递推公式 --> 这一步就是在规划方法来寻找最优值（解）
3.确定递推遍历的顺序 --> 这是在确定如何寻找到每一个可行解
4.dp数组初始化 --> 在一般情况下，递推公式可能不能包括所有可行解的情况，或者需要对问题中的值进行一个初始化赋值，以来正确进行递推。
三、动态规划LeetCode经典题目和延伸知识算法
1.斐波那契数 509
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。
示例 1：
输入：n = 2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1
- class Solution {
- public:
- int fib(int n) {
- if(n <= 1){
- return n;
- }
- vector<int> result(n+1);
- result[0] = 0;
- result[1] = 1;
-
- for(int i = 2;i <= n;i++){
- result[i] = result[i-1] + result[i-2];
- }
-
- return result[n];
- }
- };
题解：
动态规划类题目，确定好dp数组的含义为斐波那契数列，递推公式是前两个元素相加，顺序是从前至后 ，然后按照题目要求，求对应位置的dp数值即可
2.爬楼梯 70
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶
- class Solution {
- public:
- int climbStairs(int n) {
- if(n<=2){
- return n;
- }
- vector<int> result(n+1);
- result[1] = 1;
- result[2] = 2;
-
- for(int i = 3;i <= n;i++){
- result[i] = result[i-1]+result[i-2];//楼梯数组递推公式
- }
-
- return result[n];
- }
- };
题解：
首先确定dp数组的含义是爬楼梯阶层可能的方法数，递推公式根据常识可以得到，该阶层的方法数等于前一个阶层走一步+前两个的阶层走两步这两种大可能的相加，即可发现数列其实为斐波那契数列，接着进入for循环递推即可
3.使用最小花费爬楼梯 746
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 1：
输入：cost = [10,15,20] 输出：15 解释：你将从下标为 1 的台阶开始。 - 支付 15 ，向上爬两个台阶，到达楼梯顶部。 总花费为 15 。
- class Solution {
- public:
- int minCostClimbingStairs(vector<int>& cost) {
- vector<int> dp(cost.size()+1);
- dp[0]=0;
- dp[1]=0;//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]);
- }
- //dp要计算到cost的size索引，因为最后一步要跳到顶上去
-
- return dp[cost.size()];
- }
- };
题解：
dp数组的含义为到i位置所需要的体力值，递推公式是前一个位置和前两个位置的消耗体力值再加上各自跳起所需要的体力。值得注意的是，最后需要跳到楼顶上，所以遍历需要到目标cost的长度才可。并且因为需要花费最小，设置初始化中0和1索引下花费皆为0（1可以不为0但是没必要）
4.不同路径 62
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7 输出：28
- class Solution {
- public:
- int uniquePaths(int m, int n) {
- //定义二维数组
- vector<vector<int>> result(m,vector<int>(n,0));
-
- //初始化
- for(int i =0;i<m;i++){
- result[i][0] = 1;//为了可以向下推导
- }
- for(int i = 0;i<n;i++){
- result[0][i] = 1;//为了可以向右推导
- }
-
- for(int i = 1;i<m;i++){
- for(int j =1;j<n;j++){
- result[i][j] = result[i-1][j]+result[i][j-1];//因为只能向下向右移动一步，所以可以反推当前的可能性为其相加
- }
- }
-
- return result[m-1][n-1];
- }
- };
题解：
首先明白dp数组的含义，在这里指的是到当前位置时，可以行走的路径条数(这很重要）。根据题目中，只能下向下或者向上，所以可以初始化两边，两边的每一个位置的值，其实都是1，因为到该位置只能向右或者向下，利用这一特性可以将dp数组的两边初始化完成。接下来只需要按照递推公式，即当前位置的路径条数等于左边一格的路径条数加上上面一格的路径条数就可以完成遍历赋值，最终返回最后一个元素即可。
5. 不同路径2 63
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
- class Solution {
- public:
- int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
- int m = obstacleGrid.size();
- int n = obstacleGrid[0].size();
- if(obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1){
- return 0;//不再存在路径了
- }
- vector<vector<int>> result(m,vector<int>(n,0));
- for(int i =0;i < m && obstacleGrid[i][0] != 1;i++){
- result[i][0] = 1;//当前位置不是障碍物时候
- }
-
- for(int i =0;i < n && obstacleGrid[0][i] != 1;i++){
- result[0][i] = 1;//当前位置不是障碍物时候
- }
-
- for(int i =1;i < m ;i++){
- for(int j =1;j < n ;j++){
- if(obstacleGrid[i][j] == 1){
- //如果当前位置是障碍物
- continue;
- }
- result[i][j] = result[i-1][j]+result[i][j-1];
- }
- }
-
- return result[m-1][n-1];
-
- }
- };
题解：
该题与不同路径的区别在于，需要对障碍物进行判断，首先体现在一开始的判定，如果障碍物为初始或者终点，那么不可能存在路径。其次在初始化的时候，如果本身一条路走到黑的下路和右路被阻碍，那么一旦被阻碍就一定不是1条路径的解了。最终遍历递推公式赋值的时候，也要注意避开障碍物，但是不用一旦阻碍就退出，因为可以通过其附近的非障碍物到达终点。
6.不同的二叉搜索树 96
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3 输出：5
- class Solution {
- public:
- int numTrees(int n) {
- //1时：左子树（0个）*右子树（2个）
- //2时：左子树（1个）*右子树（1个）
- //3时：左子树（2个）*右子树（0个）
- 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];//累加得相当于1、2、3...i的数值和
- }
- }
-
- return dp[n];
- }
- };
题解：
本题需要寻找到dp数组的含义，在这里指的就是当前值下，二叉树的长度为当前的值的二叉树数量。目标长度下的二叉树数量的获取需要从长度为1开始遍历，累加每一个值下的二叉树数量。并且当前长度下的二叉树数量在累加之后，互相通用（隐藏了需要顺序遍历的条件）。在初始化上，只需要定义0长度下的二叉数数量（没有子树）为1（只有一种可能性）即可，因为后面都可以通过累加或者相乘获得。在递推公式上，通过比较可以得到一个关系，即当前值作为二叉树的长度，二叉树的可能数量为 = 之前的二叉树长度小于该值的二叉树数量的累加+（左子树长度为当前长度减去-1的可能数量）*（右子树长度为总长度减去当前长度的可能数量）。然后按照动态规划的流程，先定义后初始，最终递归返回结果。
7. 01背包概念介绍
背包最大重量为4。
物品为：
| 重量 | 价值 | |
|---|---|---|
| 物品0 | 1 | 15 |
| 物品1 | 3 | 20 |
| 物品2 | 4 | 30 |
问背包能背的物品最大价值是多少？
二维数组dp
7.1.dp数组的含义
使用二维数组，即dp[i][j] 表示从下标为0到i之间的物品里任意取，放进容量为j的背包，价值总和最大是多少。
7.2.递推公式
不放该物体到背包，即背包容量为j，里面不放物品i的最大价值为dp[i - 1][j]（与前面没有包括i时候的dp数组值相同）【容量尽量充满】
放置该物体到背包，因为dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，则dp[i - 1][j - weight[i]] + value[i] 就是放置i物体后得到的最大价值【容量尽量充满的情况下，专门空出物体的重量，以此计算最大价值】
综上递推的公式为dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
7.3.初始化
dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。
那么很明显当 j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。
当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品
其他的元素因为可以靠递推出来（分别为上面的元素和左上的元素比较大小得来），所以赋值为0就可以
- // 初始化 dp
- vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
- for (int j = weight[0]; j <= bagweight; j++) {
- dp[0][j] = value[0];
- }
7.4.遍历顺序
- // weight数组的大小 就是物品个数
- for(int i = 1; i < weight.size(); i++) { // 遍历物品
- for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
- if (j < weight[i]) dp[i][j] = dp[i - 1][j];
- else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
-
- }
- }
8.01背包的一维数组dp
8.1.dp数组的定义
在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]（因为dp每个元素的值在不断递增）
8.2.dp数组的递推公式
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);可以理解为将上一层的i-1拷贝了下来
8.3.dp数组的初始化
dp[0] = 0
8.4.遍历顺序
倒序遍历是为了保证物品i只被放入一次！。但如果一旦正序遍历了，那么物品0就会被重复加入多次！
举一个例子：物品0的重量weight[0] = 1，价值value[0] = 15
如果正序遍历
dp[1] = dp[1 - weight[0]] + value[0] = 15
dp[2] = dp[2 - weight[0]] + value[0] = 30
此时dp[2]就已经是30了，意味着物品0，被放入了两次，所以不能正序遍历。
为什么倒序遍历，就可以保证物品只放入一次呢？
倒序就是先算dp[2]
dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp数组已经都初始化为0）
dp[1] = dp[1 - weight[0]] + value[0] = 15
所以从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了
综上代码最终为
- void test_1_wei_bag_problem() {
- vector<int> weight = {1, 3, 4};
- vector<int> value = {15, 20, 30};
- int bagWeight = 4;
-
- // 初始化
- vector<int> dp(bagWeight + 1, 0);
- for(int i = 0; i < weight.size(); i++) { // 遍历物品
- for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
- dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
- }
- }
- cout << dp[bagWeight] << endl;
- }
-
- int main() {
- test_1_wei_bag_problem();
- }
9.分割等和子集 416
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11]
- class Solution {
- public:
- bool canPartition(vector<int>& nums) {
- //价值数组--容量为j的背包，价值最大为dp[j]--一维的含义
- vector<int> dp(10001,0);//200*200/2+1得到
-
- //计算元素和
- int sum = 0;
- for(int a:nums){
- sum += a;
- }
- if(sum % 2 == 1){
- return false;//一定不成立
- }
- int target = sum/2;//这是每个子集的元素和
-
- //遍历递推--元素不可重复放入，所以01背包，倒序赋值
- 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;//可以组成子集，价值最大满足
- }else{
- return false;
- }
-
-
-
- }
- };
题解：
本题需要得到集合是否能达到某特定值，那么可以使用01背包一维数组来解决问题。因为01背包可以得到大小为j的背包，所背的物品价值可以最大为dp[j]，递推条件中，元素的索引就等于其价值。所以如果背包装载正常，应该是物品价值等于大小，即dp[j]=j。在这里将重量和价值都置换为了大小
本题可以将元素和的一半（目标子集的大小）作为j，通过递推，如果得到dp[j]和需要的值相同，就说明元素总和满足条件，即子集满足条件成立。通过比较获得一定元素组合下价值最大的背包可以装载大小为元素和一半的元素，那么剩下来的元素就构成了另一个子集
10. 最后一块石头的重量2 1049
有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
- 如果
x == y，那么两块石头都会被完全粉碎； - 如果
x != y，那么重量为x的石头将会完全粉碎，而重量为y的石头新重量为y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
示例 1：
输入：stones = [2,7,4,1,8,1] 输出：1 解释： 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]， 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]， 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]， 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
- class Solution {
- public:
- int lastStoneWeightII(vector<int>& stones) {
- vector<int> dp(1501,0);//定义大小为元素总和边界一半的dp数组
- int sum = 0;
- for(int a:stones){
- sum += a;
- }
- int target = sum/2;//向下取整，获取stone总和的一半
-
- 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]);//仍然是重量x和价值y都和元素大小相同
- }
- }
-
- //尽可能朝一半的总和靠近
- int minweight = 0;
- minweight = sum - dp[target]*2;
- return minweight;
- }
- };
题解：
如果将数组分成近乎相同的两个数组，然后放在一起碰撞，那么一定会得到最小的结果。而且本题和分割等和子集相似，都可以将重量x和价值y化为元素对应的大小，那么只要定义好一半的大小，让dp【j】尽可能装石头，得到最大的值，那就是在一定的组合下，最靠近一半的值。最后只需要将原本数组的总和减去最靠近一半的值的两倍即可得到碰撞后剩下的最小值。
11.01背包总结
01背包的一维式子，其重量作为索引(x)，其价值作为索引对应的值(y)。每次递推的时候，会判断值不值得加入重量对应的价值。所以当索引为重量之和的时候，索引对应的值也就是其最大价值之和
在上面两题中，价值（y）=重量（x）=大小，题意想让大小为特定值，那么只要获取到索引为特定值并且其对应的价值（y）为特定值即可。虽然看起来很绕，但是这是建立在三者相同的情况下
12. 目标和 494
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
- 例如，
nums = [2, 1]，可以在2之前添加'+'，在1之前添加'-'，然后串联起来得到表达式"+2-1"。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 1：
输入：nums = [1,1,1,1,1], target = 3 输出：5 解释：一共有 5 种方法让最终目标和为 3 。 -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3
- class Solution {
- public:
- int findTargetSumWays(vector<int>& nums, int target) {
- //用于加法集合left，用于减法的数集合right(sum-left)
- //left-（sum-left） = target ---> left = (sum+target)/2
-
- int sum =0;
- for(int a: nums){
- sum += a;
- }
- if((sum+target)%2 ==1 || abs(target) > sum){
- return 0;//不存在解
- }
- int bagsize = (sum+target)/2;//背包装这么大就可以
- vector<int> dp(bagsize+1,0);//dp数组的含义是，当前容量j（=索引）下可以获得dp[j]种组合--容量不要开的太大
- dp[0] = 1;//0容器，下可获得一种解
- for(int i =0;i<nums.size();i++){
- //对每个结点的重量进行运算
- for(int j = bagsize;j>=nums[i];j--){
- dp[j] += dp[j-nums[i]];//dp[j]=(1)dp[j-1]+(2)dp[j-2]+(3)dp[j-3]+(4)dp[j-4]...
- }
- }
-
- return dp[bagsize];
-
- }
- };
题解：
本题需要测出数组中的元素如何组合，达到要求。由于只对数组中的元素各取一次，所以可以采用01背包的方法。dp数组的含义为当前容量j（=索引）下可以获得dp[j]种组合。初始化中容量j为0.那么在有解的情况下，只有可能一解（，实际上不是真的要求容量为0下讨论，这个j为0出现的情况是，数组为[0]，target=0，所以只有0这样的一个解）。递推公式上，dp的索引下，是之前每次索引减小的对应dp的累加和，因为解是由他们组成的，同理他们的组合也是由比其本身小的累加而成。遍历顺序上，为了避免累加重复，所以使用后序遍历。然后在一开始要对无解的情况进行排除(也是为了dp数组初始化的正确性）都是整数，则需要保证整除，或者是target绝对值不能大于计算后总和之类的
13.一和零 474
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
示例 1：
输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
- class Solution {
- public:
- int findMaxForm(vector<string>& strs, int m, int n) {
- vector<vector<int>> dp(m+1,vector<int>(n+1,0));//全部初始化为0，dp的含义为当前容量下，装载了多少个物品==子集的长度
-
- //遍历物品
- for(string str :strs){
- int oneNum = 0,zeroNum = 0;
- for(char a : str){
- if(a=='0'){
- zeroNum++;
- }else{
- oneNum++;
- }
- }
-
- //遍历背包
- for(int i =m;i >=zeroNum;i--){
- for(int j =n; j>=oneNum;j--){
- dp[i][j] = max(dp[i][j],dp[i-zeroNum][j-oneNum] +1);//把当前物品的重量减去，放新的物品,求最大的数量
- }
- }
- }
-
- return dp[m][n];//当前容量下的物品(子集个数)
-
-
- }
- };
题解：
本题dp数组的含义是，在最多m个0和n个1的情况下，可以存在的最长长度的子集。注意该题的讨论对象是0和1的最多出现次数。所以每个字符串就是物品，是该物品时，其对应最多1和0的子集的长度情况。递推公式就是讨论，该最多1和最多0的情况下，将该物品移除谁更大，从而判断是否装入背包。在遍历顺序中是需要找到，子集的长度，由于子集中最多有m个0和n个1，所以需要保证子集中的0和1的数量不能超过m和n，该物体的下标一定都要大于子集字符串中原本的0和1数量，否则不能进行物品移除的判断。初始化各个情况下的子集长度都为0.
注意点
该题物品为字符串的原因是，需要讨论字符串的子集数，每个字符串都可能增加各个情况下的子集长度
总结：
01背包问题多变，但是每一题都是要先确定物品和dp数组的含义，在遍历的时候也是先遍历物品后遍历背包的容量，而且递推的公式一定和该物品有关(基本都是减去该物品，来判断是否装入)接着根据递推的公式代入遍历中既可
14.完全背包介绍
完全背包可以使用元素无数次 --正序遍历
先遍历物品后遍历背包（组合），和先遍历背包，后遍历物体（排列）都可以
15.零钱兑换2 518
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例 1：
输入：amount = 5, coins = [1, 2, 5] 输出：4 解释：有四种方式可以凑成总金额： 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1
- class Solution {
- public:
- int change(int amount, vector<int>& coins) {
- //本题其重量和价值相同
- vector<int> dp(amount+1,0);//代表总面额达到要求时候的方法数--大小加1
- dp[0] = 1;//因为计算dp【1】的时候，dp【1】按理是为1，因为要实现正序+=1的成立
- for(int i = 0; i< coins.size();i++){
- for(int j = coins[i];j<=amount;j++){
- dp[j] += dp[j-coins[i]];//对当前的物体进行装载背包的操作---由于是组合的问题，则不用比较大小
- }
- }
-
- return dp[amount];
- }
- };
题解·：
本题是组合类问题，求取满足大小的组合数。那么就可以采用完全背包的思想，并且由于不是要取最优解，那么就不用在递推内比较大小。dp[j]的含义是当总面额达到j的时候，其面额内的组合数即为所求。这是对每一个物体一层层遍历赋值，不断累加后获得到的最终结果。从当前物体的重量开始不断累加可能性，获取dp【j】==当加上物体重量后，其对应的值也就是累加其未加上该重量的价值然后一层层向后累加，获取当前容量下的价值，并且当最终遍历到dp【amout】的时候，其已经由dp【amout-coin【i】】的累加组成。（coins[i]为coins数组的所有解）
16.组合总和4 377
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
示例 1：
输入：nums = [1,2,3], target = 4 输出：7 解释： 所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) 请注意，顺序不同的序列被视作不同的组合。
- class Solution {
- public:
- int combinationSum4(vector<int>& nums, int target) {
- vector<int> dp(target+1,0);
-
- dp[0] = 1;//为了dp【1】为1
- for(int i=0;i<=target;i++){
- for(int j =0;j<nums.size();j++){
- if(i-nums[j] >=0 && dp[i] < INT_MAX - dp[i-nums[j]]){//存在超过target的无解情况/并且不能超过int的范围32位
- dp[i] += dp[i-nums[j]];//j索引对应了目标数
- }
- }
- }
-
- return dp[target];
- }
- };
题解：
根据题意求的任选元素后，满足相加和为目标值的排列数，并且本题与零钱兑换相同，都是价值重量相同的情况。所以为了能得到排列的所有情况，所以本题采用先遍历背包后遍历物体的情况，以来包括所有的情况，逐步得到当前元素子集的排列可能性，然后向后累加。每层分别累加上dp[i]前一个（实际上是减去重量的索引）的其累加值，这样可以获取到当加上该数值/重量后对应解的数量，只要i不大于target，那么它就在朝着构成它的解的方向赋值
17.零钱兑换322
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
- class Solution {
- public:
- int coinChange(vector<int>& coins, int amount) {
- vector<int> dp(amount+1,INT_MAX-1);//为了求最小值，全部初始化为最大int-1.为了后面的遍历，正常进行
- //dp数组的含义是当前金额下的最小硬币个数
-
- dp[0] = 0;//从测试用例中可见，如果目标和为0，那么硬币个数自然为0
-
- for(int i=0;i<coins.size();i++){
- for(int j = coins[i];j<=amount;j++){
- dp[j] = min(dp[j-coins[i]]+1,dp[j]);//重量为coin【i】，价值为1--一个硬币
- }
- }
-
- if(dp[amount] == INT_MAX -1){
- return -1;//没有解
- }
- return dp[amount];
- }
- };
题解：
本题仍然是采用完全背包的思路，因为面额是不限制取的次数的，并且由于题意需要组合，所以遍历顺序是先遍历物品后遍历背包。dp数组的含义就是当前总金额下，花费最少硬币的组合。这类值的问题，需要确定好重量==硬币数组对应的值，价值==个数（默认每次加一），从而在每一次赋值时确定当前那种方案最省（是保留之前的解，还是加一减去当前物品面额）。同时注意在获取最小值的初始化上，要将每个元素初始为INT_MAX-1，这样方便最小值的比较，并且方便最后无解的获取。在测试用例中，可见dp[0]=0，这个是要特殊初始化的
18.完全平方数 279
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
- class Solution {
- public:
- int numSquares(int n) {
- int result;
- vector<int> dp(n+1,INT_MAX-1);
- dp[0] = 0;// 为了n =1的时候，能够式子成立
- //物品为iXi,dp数组的含义是当前大小下的数量
- for(int i = 1;i*i <=n;i++){
- for(int j = i*i;j<=n;j++){
- dp[j] = min(dp[j],dp[j-i*i] +1);//如果不装该物体
- }
- }
-
- return dp[n];
- }
- };
题解：
本题实质上 = 背包问题中求最小价值。首先确定dp数组的含义是当前容量下，对应最小的价值（最少的数量）。初始化中注意一定要特别定义索引为0的值，因为在遍历装载的时候一定会用到dp【0】，使得dp【1】为1，就设置dp【0】为 0 ，其他的统一为INT_MAX-1，确保取到最小的值。在递推公式上，就是判断当前背包装载了该物体（i*i)与否，价值谁最小优先取谁。并且题目对顺序没有要求，则用先遍历后遍历背包的遍历顺序
19.单词拆分 139
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"] 输出: true 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
- class Solution {
- public:
- bool wordBreak(string s, vector<string>& wordDict) {
- vector<bool> dp(s.size()+1,false);//当前索引下是否可以正确组成--默认都不可以，等待后面的刷新赋值
- unordered_set<string> wordAll(wordDict.begin(),wordDict.end());//转换为无序集合
-
- dp[0] = true;//确保正常遍历
-
- for(int i =1;i<=s.size();i++){//先背包后物体-->这是排列（有顺序）从开始，为了子串可裁剪
- for(int j =0;j<i;j++){
- string thisS = s.substr(j,i-j);//截取出-开始位置，长度
- if(wordAll.find(thisS) != wordAll.end() && dp[j]== true){
- dp[i] = true;//如果在集合中寻找到字符串或者子串，并且前置的索引也满足了条件
- }
- }
- }
-
- return dp[s.size()];
-
- }
- };
题解：
本题是需要确定出目标字符串是否可以由子串组成，那么可以转换为当前大小的背包是否可以由物品装满，这里应该是进一步是否正确的装满，可以重复选，则确定为。dp数组的含义则为，当前大小下的背包，可否由字符串（物体）们拼接而成。要实现这样的功能，则需要利用无序集合中的find寻找目标字符串。如果找到了就赋值为真，然后通过不断的截取直到寻找到目标子串再次赋值为真，这也就是递推的公式。初始化中除了索引0为真外，其他全部为false，原因是后序判断赋值的时候，至少需要索引0为真才能有第一个真以进行遍历。在遍历顺序上，由于要拼接成固定的字符串，所以是在求排列，遍历顺序则为先遍历背包后遍历物体，保证每种顺序包括。
20.打家劫舍 198
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
- class Solution {
- public:
- int rob(vector<int>& nums) {
- //剪枝
- if(nums.size()== 0){
- return 0;
- }
- if(nums.size()==1){
- return nums[0];//直接进入就可以
- }
- //dp数组的含义，当前房屋所能偷窃到的最高金额
- vector<int> dp(nums.size()+1,0);
-
- //初始化--为了递推公式存在
- dp[0] = nums[0];
- dp[1] = max(nums[0],nums[1]);
-
- for(int i = 2;i<nums.size();i++){
- dp[i] = max(dp[i-1],dp[i-2]+nums[i]);//分为2种情况，一种是不偷第i个房间，即当前金额应该为前一个房间索引对应的值
- //另一种情况，偷第i个房间，那么一定不能考虑前一个房间，至少从前两个房间开始考虑，也就是前两个房间索引对应的值加上i个房间的金额
- }
-
- return dp[nums.size()-1];
- }
- };
题解：
本题讨论最高金额，并且打家劫舍也是只能进入一次，所以可以使用01背包的思路进行解决。dp数组的含义是，当前房间索引下，可以偷到的最高金额。递推公式上，需要对当前的金额进行判断最高，可以简单分为两种情况，一，当前房间不偷，那么就看前一个房间下的索引的值即可（前一个房间不一定被偷了，但是看最大的比较只需要前一个的值即可）二、当前房间要偷，那么前一个房间一定不能偷，所以这样的值就是前两个房间下的索引加上该房间的金额即可，这也就是背包问题中的判断当前物体能否装载。遍历顺序上由于递推公式上，需要前几个的值，所以采用顺序方式遍历。初始化上，因为递推公式的特殊，所以需要提前定义好dp【0】和的dp【1】的值，便于计算
21.打家劫舍2 213
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例 1：
输入：nums = [2,3,2] 输出：3 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
- class Solution {
- private:
- int GetResult(vector<int>& AimNums,int start,int end){
- //额外剪枝
- if(start == end){
- return AimNums[start];//已经重复（总共2个元素的时候），如果继续向下会没有解--start+2
- }
-
- //对传入的数值进行分析
- vector<int> dp(AimNums.size());//定义固定大小的dp数组,默认值为0
- dp[start] = AimNums[start];
- dp[start+1] = max(AimNums[start],AimNums[start+1]);//定义好初始的值
- for(int i = start+2;i<=end;i++){
- dp[i] = max(dp[i-1],dp[i-2]+AimNums[i]);
- }
- return dp[end];
- }
-
- public:
- int rob(vector<int>& nums) {
- if(nums.size() == 0){
- return 0;
- }
- if(nums.size() == 1){
- return nums[0];
- }
- int leftMax = GetResult(nums,0,nums.size()-2);//除了最右不考虑
- int rightMax = GetResult(nums,1,nums.size()-1);//除了最左不考虑
- return max(leftMax,rightMax);
- }
- };
题解：
本题和打家劫舍的区别就是，这里将首尾相连了，也就是首尾不可能同时考虑，所以可以巧妙的对没有首和没有尾的两个数组进行打家劫舍的讨论，最后取两者的最大值即为最终的解。虽然是环形，但是每个房间只能进入一次， 所以逻辑上没有太大区别。定义一个讨论的函数，记得在内部做判断，判断传入的首尾位置是否相同，为了递推公式的进行（start+2），如果相同，在dp数组的初始化中会造成歧义（因为在考虑右边界的时候，如果只有两个元素，start+1是在数组中不存在的，这就会报红错，超过范围），并且最终返回的时候，也会返回出错。其他的只需要使用讨论函数中的dp数组进行递推得到其最大值即可。最后放入主函数中，一起比较大小。
22.打家劫舍3 337
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
示例 1:
输入: root = [3,2,3,null,3,null,1] 输出: 7 解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
- class Solution {
- private:
- vector<int> GetResult(TreeNode* cur){
- //终止条件
- if(cur == nullptr){
- return {0,0};
- }
- //dp【0】为不偷当前节点的总金额，dp【1】为偷当前节点的总金额
- vector<int> leftdp = GetResult(cur->left);
- vector<int> rightdp = GetResult(cur->right);
- //处理逻辑
- int leftVal =max(leftdp[0],leftdp[1])+max(rightdp[0],rightdp[1]);//不偷当前的节点，则可选择偷左右的节点
- int rightVal = cur->val+leftdp[0]+rightdp[0];//偷当前节点，子节点不偷
-
- return {leftVal,rightVal};
- }
- public:
- int rob(TreeNode* root) {
- vector<int> finalNum = GetResult(root);
- return max(finalNum[0],finalNum[1]);
- }
- };
题解：
本题为树形dp类型题目，其本质还是要用到背包思维，如何装才能装的最多。具体体现在递推逻辑上，对该节点是否装入进行讨论，如果不装入该节点（不偷），那么就装入其子节点的金额（通过递归已经获得，也可以选择不装入，需要通过max判断那种更好，这里也是背包的体现）；如果装入该节点，则应加上没有装入其子节点的金额和本身的金额。记得递归需要设置终止条件。递归完成后，对获得的结果进行比较，返回大者即为解（结果就是讨论装入root根节点与否）
23.买卖股票的最佳时机 121
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
- class Solution {
- public:
- int maxProfit(vector<int>& prices) {
- //定义dp数组，代表当前索引下的利润
- vector<vector<int>> dp(prices.size()+1,vector<int>(2,0));//定义二维数组dp，用来保存当前索引下持有了股票与否
- //初始化数组--便于比较
- dp[0][0]= -prices[0];
- dp[0][1]= 0;
- //遍历--从1开始防止越界
- for(int i =1;i<prices.size();i++){
- //当前索引下，持有股票
- dp[i][0] = max(dp[i-1][0],-prices[i]);//判断最小的股票价格-利益最大化
- //当前索引下，不持有股票
- dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i]);//卖出前后金额哪个多
- }
-
- return max(dp[prices.size()-1][0],dp[prices.size()-1][1]);
- }
- };
题解：
本题要求得到的最高利润，那么可以用dp来规划解决。dp数组的含义是当前索引下可以获得的最高利润。但是仅仅这样定义，是无法再递推公式中体现的，因为利润受到当前索引下的股票的约束和当前持有股票的状态的约束。所以需要定义dp数组为二维，表示当前索引下，持有股票与否，与其对应的利润。而递推条件就是，在当前索引下，持有股票下，是否持有当前的股票会更划算（花的钱更少），不持有股票下，是卖出当前股票（对应之前已经有持有股票情况下）还是不卖，保持之前未持有的状态，哪个利润更高。本题需要注意的点是初始化需要定义好dp【0】下两个状态的值，dp【i】【0】始终持有股票。
24.买卖股票的最佳时机三 123
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入：prices = [3,3,5,0,0,3,1,4] 输出：6 解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。 随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3
- class Solution {
- public:
- int maxProfit(vector<int>& prices) {
- //定义dp数组--五状态二维数组
- vector<vector<int>> dp(prices.size(),vector<int>(5,0));
- //初始化数组
- 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<prices.size();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 max(dp[prices.size()-1][2],dp[prices.size()-1][4]);
-
- }
- };
题解：
本题需要讨论最高利润，但同时要考虑到可以多买一张的情况，所以这题的dp数组需要多设置买了两次的状态，dp数组的含义就是在当前状态下，可以获得的最高利润是多少。递推公式中，都是判断当前进行对应状态的操作是否会使利润最大化，例如第一次买入的状态，就要和该状态之前的利润和买入当前股票（建立在之前没有买过股票的情况）进行一个比较。遍历顺序上，顺序遍历使得dp的值不断比较变化即可。最后对最高利润的两种状态（第一次卖出，第二次卖出）进行比较即可
25.买卖股票的最佳时机4 188
给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1：
输入：k = 2, prices = [2,4,1] 输出：2 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
- class Solution {
- public:
- int maxProfit(int k, vector<int>& prices) {
- int length = prices.size();
- //dp数组动态定义
- vector<vector<int>> dp(length,vector<int>(2*k+1,0));
- //dp数组动态初始化
- for(int i=1;i<2*k;i+=2){
- dp[0][i] = -prices[0];
- }
-
- //递推动态
- for(int j=1;j<length;j++){
- dp[j][0] = dp[j-1][0];
- for(int m=1;m<2*k;m+=2){
- dp[j][m] = max(dp[j-1][m],dp[j-1][m-1]-prices[j]);//当前奇数--买入
- dp[j][m+1] = max(dp[j-1][m+1],dp[j-1][m]+prices[j]);//当前偶数--卖出
- }
- }
-
- return dp[length-1][2*k];
- }
- };
题解：
本题其实就是买卖股票3的动态版，其实就是把固定的可买次数变成了动态。具体体现于在定义的时候，将数组的横向空间大小定义为2k+1(无操作+买卖)，在初始化的时候，将买入的状态全部初始化为-prices【0】（买入一定为奇数索引），在递归的时候，遍历2*k，并且对其中买入卖出（对应奇偶数）进行相应的价值加减与判断值得进行对应的操作与否。最终在返回值的时候，不需要再比较哪次卖出的利润最大，初始的卖出利润都是为0，都是考虑的当天买当天卖，所以如果卖出出现利润，那么后续的买入就会去考虑，这样的买入会不会盈利（跟之前的买入相比，初始买入都是负数），则后续的卖出也会和之前的卖出相比（我卖出这次的买入，跟之前相比，会不会盈利），可见初始下，即使后续买入了，只要前面卖出盈利比后续卖出更大，那么后续的买入又会被立刻卖出，以保持各次最大利润的效果。这就是牵一发动全身，所有的卖出都时刻保持在当前卖出的最高值上
26.买卖股票的最佳时机含冷冻期
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
- class Solution {
- public:
- int maxProfit(vector<int>& prices) {
- //dp[i][0]持有股票
- //dp[i][1]今天卖出股票
- //dp[i][2]冷冻期
- //dp[i][3]已卖出股票
- vector<vector<int>> dp(prices.size(),vector<int>(4,0));
-
- dp[0][0] = -prices[0];
-
- for(int i=1;i<prices.size();i++){
- dp[i][0] = max(dp[i-1][0],max(dp[i-1][3]-prices[i],dp[i-1][2]-prices[i]));//保持之前、卖出后买入、冷冻期后买入
- dp[i][1] = dp[i-1][0] + prices[i];//之前持有的情况下卖出
- dp[i][2] = dp[i-1][1];//之前卖出了之后就是冷冻期
- dp[i][3] = max(dp[i-1][3],dp[i-1][2]);//继续保持、前一天为冷冻期
- }
-
- return max(dp[prices.size()-1][3],max(dp[prices.size()-1][1],dp[prices.size()-1][2]));
- }
- };
题解：
这类买卖股票的题目，主要是对于各种状态的的讨论。本题由于存在冷冻期，则可以分成四个状态。 买入了股票、刚卖出了股票、冷冻期、卖出股票的状态。这几个状态彼此联系，例如买入股票状态，需要建立在冷冻期之后或者卖出股票状态之后。刚卖出股票，需要建立在买入股票之上。冷冻期，需要建立在刚卖出了股票之后。卖出股票状态，需要建立在冷冻期之后。那么dp动态规划数组也是二维，用来保存第i天下的四个状态。初始化也和经典买卖股票一样，先设置初始为买入，便于之后的遍历赋值。
27.买卖股票的最佳时机含手续费 714
给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
示例 1：
输入：prices = [1, 3, 2, 8, 4, 9], fee = 2 输出：8 解释：能够达到的最大利润: 在此处买入 prices[0] = 1 在此处卖出 prices[3] = 8 在此处买入 prices[4] = 4 在此处卖出 prices[5] = 9 总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8
- class Solution {
- public:
- int maxProfit(vector<int>& prices, int fee) {
- //定义dp数组，在当前天数下的状态对应利润
- vector<vector<int>> dp(prices.size(),vector<int>(2,0));
- //初始化dp数组
- dp[0][0] = -prices[0];
- //递推
- for(int i = 1;i < prices.size();i++){
- dp[i][0] = max(dp[i-1][0],dp[i-1][1] -prices[i]);
- dp[i][1] = max(dp[i-1][1],dp[i-1][0] +prices[i] - fee);
- }
-
- return max(dp[prices.size()-1][1],dp[prices.size()-1][0]);
- }
- };
题解：
本题需要注意的点就是手续费需要在卖出之后减去。其他的步骤就和经典股票题目一样。dp数组代表最大的利润，然后通过递推比较大小来讨论两个状态下的最大利润。最后由于卖出的状态下还要减去手续费，所以不确定是最大的，最终结果进行比较大小，返回大的即可
28.最长递增子序列 300
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
- class Solution {
- public:
- int lengthOfLIS(vector<int>& nums) {
- //定义dp数组为，以当前索引下的元素为末尾的序列的最长长度
- vector<int> dp(nums.size(),1);//默认为1
- //递推公式
- int result = 0;
- for(int i =0;i<nums.size();i++){
- for(int j = 0;j<i;j++){
- if(nums[j]<nums[i]){
- //在序列中找到最长的递增序列
- dp[i] = max(dp[i],dp[j]+1);
- }
- }
- result = max(result,dp[i]);
- }
-
- return result;
- }
- };
题解：
注意题目是求子序列的长度，所以只要按顺序逐一遍历元素，通过遍历比较之前子序列的长度，并且增加对应长度，如果小于就算入长度即可。定义dp为以当前索引下的元素作为末尾的子序列的最长长度。在初始化方面，每个元素自身就是一个子序列，所以都默认为1。递推公式上，为了当前元素后面被遍历比较，需要时刻保证该元素为当前最大，遍历该元素之前的所有元素，只要小于就判断序列的长度何时最大（小于的元素序列加一，还是保持自身序列数量不变）。最终因为dp数组含义是元素索引下的最大值，所以最后一个元素索引下dp不一定是最大的值，因此在递推的时候时刻判断赋值最大值即可。
29.最长连续递增序列 674
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。
示例 1：
输入：nums = [1,3,5,4,7] 输出：3 解释：最长连续递增序列是 [1,3,5], 长度为3。 尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。
- class Solution {
- public:
- int findLengthOfLCIS(vector<int>& nums) {
- vector<int> dp(nums.size(),1);//定义加初始化
- int result = 1;
- //递推公式
- for(int i = 1;i<nums.size();i++){
- if(nums[i]>nums[i-1]){
- dp[i] = dp[i-1]+1;
- }
-
- result = max(result,dp[i]);
- }
-
- return result;
- }
- };
题解：
本题需要求连续的子序列长度，那么和最长递增子序列的区别就在于一个需要去遍历在当前位置之前的所有元素，找到最长的长度的那一个，而本题只需要比较前一个，就能达到获得连续子序列长度最长的效果。dp数组仍然定义为当前位置的最长子序列长度。而递推公式则只需要在遍历目标数组的过程中，每次和前一个比大小即可，如果满足在递增，就将小的dp值（其递增序列长度）+1然后赋值给大的即可。记得最大值也要在比较的时候时刻保存，默认为1（一个数字）
30.最长重复子数组 718
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
示例 1：
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7] 输出：3 解释：长度最长的公共子数组是 [3,2,1] 。
- class Solution {
- public:
- int findLength(vector<int>& nums1, vector<int>& nums2) {
- //先定义二维数组，代表的是nums1【i-1】为首的，以nums2【j-1】为末尾的最长子数组的长度
- vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,0));
-
- int result = 0;//存在为0的可能性
-
- //递推公式
- for(int i=1;i<=nums1.size();i++){
- for(int j=1;j<=nums2.size();j++){
- if(nums1[i-1] == nums2[j-1]){
- dp[i][j] = dp[i-1][j-1]+1;//从后往前赋值
- }
- result = max(dp[i][j],result);
- }
- }
-
- return result;
- }
- };
题解：
本题需要定义好dp数组的含义。在这里dp数组是指，以nums【i-1】为首的，以nums【j-1】为末尾的最长重复子数组的长度。因为可能没有任何重复，初始化为0，包括需要时刻刷新的result值，也要初始化为0。最重要的是递推公式，因为是二维数组，所以嵌套遍历，在两者在各自索引-1下的值相同的时候，也就是该索引前面一个数值相同时，那么就出现了重复数组，这时候对该索引下的dp数组赋值加1即可。(这dp[i][j]就是代表了dp【i-1】【j-1】对应的长度，这样写，对代码更简洁）
用i、j指代对应i-1、j-1的索引，是因为如果不这样的话，直接进行递推考虑不到所有结果，【i-1】【j-1】的值就需要完全初始化过一行一列。而指代之后，就会遍历到每一种情况
31.最长公共子序列 1143
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
- 例如，
"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1：
输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace" ，它的长度为 3 。
- class Solution {
- public:
- int longestCommonSubsequence(string text1, string text2) {
- //在dp数组的含义中，代表了最长公共子序列的长度在[0,i-1]和[0,j-1]的两个字符串中
- vector<vector<int>> dp(text1.size()+1,vector<int>(text2.size()+1,0));
- for(int i =1;i<=text1.size();i++){
- for(int j =1;j<=text2.size();j++){
- if(text1[i-1] == text2[j-1]){
- dp[i][j] = dp[i-1][j-1]+1;
- }else{
- dp[i][j] = max(dp[i-1][j],dp[i][j-1]);//如果当前长度下对应值不同，删除部分字符后获取最大值
- }
-
- }
- }
-
- return dp[text1.size()][text2.size()];
- }
- };
题解：
这题和重复数组有着异曲同工之妙，同样是要获得两个数组、字符串的相同部分，不同的是重复数组是不可以删除元素的，也就是需要绝对的顺序。而本题的子序列可以删除元素，所以不用完全对应，只需要存在重复的元素序列就可以。所以本题体现的变化首先在递推公式上，首先判断当前索引下两者是否相同，这是最理想的情况，当然如果不相同可以去比较，各自“删除”一个元素后的子序列长度最大情况。因为递推公式的改变，则带来了最终返回结果时候，不需要每次再去获得最大值，可以直接返回dp定义中的字符串长度索引（对应的是i-1索引下的最大子序列长度）。dp数组的定义是当前索引下，对应字符串【0，i-1】，【0，j-1】的最长子序列长度
32.不相交的线 1035
在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。
现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足满足：
-
nums1[i] == nums2[j] - 且绘制的直线不与任何其他连线（非水平线）相交。
请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。
以这种方法绘制线条，并返回可以绘制的最大连线数。
示例 1：
输入：nums1 = [1,4,2], nums2 = [1,2,4] 输出：2 解释：可以画出两条不交叉的线，如上图所示。 但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。
- class Solution {
- public:
- int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
- //dp数组的含义是各以当前索引为长度的两个数组的最长公共子序列的长度-所以实际当前索引下是没有值的
- vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,0));
- for(int i = 1;i<= nums1.size();i++){
- for(int j = 1;j <= nums2.size();j++){
- if(nums1[i-1] == nums2[j-1]){
- dp[i][j] = dp[i-1][j-1] + 1;
- }else{
- dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
- }
- }
- }
-
- return dp[nums1.size()][nums2.size()];
- }
- };
题解：
本题需要连线起来不断开，其实就是在求一个最长的公共子序列，有了这个子序列，就可以在不影响顺序的情况下，两个数组对应的元素彼此相连，并且没有任何重复。dp数组的含义就是以当前索引作为数组的长度下，两个数组的最长子序列长度。初始化每个元素为0，因为存在没有任何公共子序列的情况。递推公式上，两数组顺序遍历，如果数组元素相同，那么就将当前dp赋值为总体前一位的dp的值+1，如果不相同，则分别删除尾部元素再次进行比较，取两者尽可能大的长度
33.判断子序列 392
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
进阶：
如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
致谢：
特别感谢 @pbrother 添加此问题并且创建所有测试用例。
示例 1：
输入：s = "abc", t = "ahbgdc" 输出：true
- class Solution {
- public:
- bool isSubsequence(string s, string t) {
- vector<vector<int>> dp(s.size()+1,vector<int>(t.size()+1,0));
-
- for(int i = 1;i<=s.size();i++){
- for(int j = 1;j<= t.size();j++){
- if(s[i-1]==t[j-1]){//包括0为索引时的解
- dp[i][j] = dp[i-1][j-1] +1;
- }else{
- dp[i][j] = dp[i][j-1];//因为是求s是不是t的子序列
- }
- }
- }
- if(dp[s.size()][t.size()] == s.size()){
- return true;
- }else{
- return false;
- }
- }
- };
题解：
本题判断子序列其实和求两个数组的最大子序列一样，只不过需要判断子序列大小是否和s的长度相同，如果相同，其实就说明了s是最大子序列，这也是正确的说明。dp数组就代表了当前索引作为长度下的两个数组的最大子序列的长度。在递推公式方面，要改变的思想是，这并不是求最长，所以在两个元素不相同的情况下，只需要将当前索引下的dp的值赋值为大序列的前一个索引的对应的dp即可（这就是单向进行比较）
34.不同的子序列 115
给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。
示例 1：
输入：s = "rabbbit", t = "rabbit"-
- 输出
3
解释：
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit
- class Solution {
- public:
- int numDistinct(string s, string t) {
- //dp数组的含义是，在当前s与t的长度下，t（实际为长度减一）可以在s中出现的次数
- vector<vector<uint64_t>> dp(s.size()+1,vector<uint64_t>(t.size()+1,0));
- //初始化
-
- //s可能有长度，t无长度，无解
- for(int i=0;i<s.size();i++){
- dp[i][0]=1;
- }
-
- //s无长度，不论t有无，皆为无解，这里就不再次赋值为0了
-
-
- //递推条件
- for(int i = 1 ;i<=s.size();i++){
- for(int j = 1;j<=t.size();j++){
- if(s[i-1]==t[j-1]){
- //当出现两个元素相同的时候
- dp[i][j] = dp[i-1][j-1]+dp[i-1][j];//考虑当前i-1索引和不考虑当前i-1索引（对应下标为i-1）
- }else{
- //没有出现两元素相同
- dp[i][j] = dp[i-1][j];//不考虑当前i-1的索引
- }
- }
- }
-
- return dp[s.size()][t.size()];
- }
- };
题解：
uint64_t是无符号64为整数，范围可以表示的2的64次方-1，而int范围可以表示到32位的整数。当然在不同位数的机器中范围也不一样，如果显示int的范围不够，那么就可以用uint64来代替int。本题是在求重复子序列上的基础上进行的延伸。首先要确定dp数组的含义，那就是在当前的长度下，对应可取的索引（长度减一）的t最多出现的次数。递推条件上，在两个索引下对应的值若相同，则dp【i】【j】对应前置的值还有加上不考虑当前索引下的s值，因为有可能前面一个元素也是和t当前的值相同，为了包括所有解，是需要加上这样一个步骤。如果两个索引下对应的值不同，则dp数组赋值为不考虑当前索引下的s值，往前一步，获得之前的值。所以根据递推公式，需要初始好【i】【0】与【0】【i】(第一行与第一列）的值，可以发现【i】【0】一定为1，【0】【i】一定为0。最终从1开始遍历，得到解。
35.两个字符串的删除操作 583
给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
示例 1：
输入: word1 = "sea", word2 = "eat" 输出: 2 解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"
- class Solution {
- public:
- int minDistance(string word1, string word2) {
- //dp数组指以i-1为尾，j-1为尾的两字符串，删除的最少次数
- vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1,0));
- //初始化--需要想到的一点是长度为0时，是需要删除全部的
- for(int i =0;i<=word1.size();i++){
- dp[i][0]=i;
- }
- for(int j = 0;j<=word2.size();j++){
- dp[0][j] = j;
- }
-
- //递推条件
- for(int i = 1;i<=word1.size();i++){
- for(int j = 1;j<=word2.size();j++){
- if(word1[i-1] == word2[j-1]){
- //当两个单词相同
- dp[i][j] = dp[i-1][j-1];//不需要操作
- }else{
- dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1);//分别对应删除i-2索引元素，删除j-2元素
- }
- }
- }
-
- return dp[word1.size()][word2.size()];
-
-
- }
- };
题解：
dp数组代表指以i-1为尾，j-1为尾的两字符串，删除的最少次数。递推条件即为，当两个元素相同的时候，则保持前置dp数组的值即可，不需要进行删除操作。但如果两个元素不同，则需要分别不考虑当前两值之一，进行“删除”，并且加上1（删除操作），比较最小的即为当前最少次数。由于是求删除次数，则在初始化的时候，需要额外考虑到，如果两个字符串其中之一是空串，那么另外一个字符串无论取何索引，其dp数组对应的值皆为索引值。
36.编辑距离 72
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros" 输出：3 解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')
- class Solution {
- public:
- int minDistance(string word1, string word2) {
- //dp数组的含义是以i-1为尾的word1，以j-1为尾的word2,，要转换所用的最少操作
- vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1,0));
- //初始化，当一个字符串为0时，转换次数为长度，因为所有的操作都可以反置
- for(int i = 0;i<=word1.size();i++){
- dp[i][0] = i;
- }
- for(int j = 0;j<=word2.size();j++){
- dp[0][j] = j;
- }
-
- //递推公式
- for(int i =1;i<=word1.size();i++){
- for(int j = 1;j<=word2.size();j++){
- if(word1[i-1] == word2[j-1]){
- dp[i][j] = dp[i-1][j-1];//不需要操作
- }else{
- dp[i][j] = min(min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+1);//对应删除与替换操作
- }
- }
- }
-
- return dp[word1.size()][word2.size()];
- }
- };
题解：
本题其实很类似于字符串的删除操作，递推条件中不同的地方在于，如果两个元素不一样，可以选择删除或者替换，这些都是一个步骤，那么就需要对删除和替换进行次数上的比较，取最小的值。在初始化中，理念也是一样的，如果字符串已经为0，那么只能执行添加或删除的操作，直到完全相同为止。
37.回文子串 647
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：s = "abc" 输出：3 解释：三个回文子串: "a", "b", "c"
- class Solution {
- public:
- int countSubstrings(string s) {
- //dp数组的含义是范围(左闭右闭)内的字符串为回文子串与否
- vector<vector<bool>> dp(s.size()+1,vector<bool>(s.size()+1,false));
- int result = 0;//定义回文子串的数量
-
- //遍历顺序由递推条件推出，得到i从下往上遍历，j从i开始向后遍历
- for(int i = s.size() - 1;i>=0;i--){
- for(int j = i;j < s.size();j++){
- if(s[i] == s[j]){
- //两边的元素索引值相同
- if(j-i <= 1){
- //三个元素或者两个元素即一定为回文子串
- dp[i][j] = true;
- result++;
- }else if(dp[i+1][j-1]){
- //如果中间的范围下认为真--回文子串
- dp[i][j] = true;
- result++;
- }
- }
- }
- }
-
- return result;
- }
- };
题解：
本题dp数组的含义是，将两个索引作为一个区间，左闭右闭，在这个区间内的字符串是否为回文子串，是则返回真，不是则返回假。递推公式上，首先要明确回文子串的含义，它是一个两边完全对称的字符串，存在中间有元素和无元素的情况，所以我们只需要判断两边的元素是否相同，如果相同则分两种情况，一种字符串很短只包括了当前两个在判断中的元素与至多一个中间元素，这样的情况一定成立，还有一种情况是，两个元素中间区间是否为真（请特别注意，由于上面的情况已经包括了两个元素间有一元素的情况，那么剩下的就一定不止一个元素，那么就一定不会超出范围的限制，导致区间错位报错）如果区间为真，也就是回文子串，那么自然加上这两个元素也是回文子串。在遍历顺序上，要考虑递推条件的话，就一定需要从后往前遍历，然后内部是从当前元素向尾部遍历，使其存在区间
38.最长回文子序列 516
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab" 输出：4 解释：一个可能的最长回文子序列为 "bbbb" 。
- class Solution {
- public:
- int longestPalindromeSubseq(string s) {
- //确定dp数组的含义是，在当前范围之下，所含有回文子序列的最长长度
- vector<vector<int>> dp(s.size()+1,vector<int>(s.size()+1,0));
-
- //初始化，索引对应值重复，则回文序列长度为1
- for(int i = 0 ; i <s.size();i++){
- dp[i][i] = 1;
- }
-
- //递推
- for(int i = s.size()-1;i>=0;i--){
- for(int j = i + 1;j < s.size();j++){
- if(s[i] == s[j]){
- dp[i][j] = dp[i+1][j-1]+2;//加上两个元素
- }else{
- dp[i][j] = max(dp[i+1][j],dp[i][j-1]);//忽略这两个的任一元素
- }
- }
- }
-
- return dp[0][s.size()-1];//返回在这段区间内的最长长度
- }
- };
题解：
本题是对求子序列的延伸。不同在于，本题求的是子序列的长度。即dp数组的含义为，在区间下的字符串中最长子序列的长度。递推公式，要分情况讨论，虽然遍历顺序和求子序列那题是一样的，还是从后往前遍历，然后再从当前索引向后遍历，达到遍历区间的效果。在区间两边元素相同的情况下，因为题目中说，可以删除，那么就直接将缩小一圈的区间+2，就一定是最长的子序列回文长度。如果不相同的话，就分别对两个元素进行删除，讨论哪个区间下的长度最长。初始化需要考虑到如果区间长度为1的情况，一定是回文长度为1，在递推公式中，该情况无法包括，所以需要单独拉出来初始化。则在最后返回的时候，只需要返回最大区间就一定是该字符串的最大长度了
