动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的，

例如：有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

动态规划中dp[j]是由dp[j-weight[i]]推导出来的，然后取max(dp[j], dp[j - weight[i]] + value[i])。

但如果是贪心呢，每次拿物品选一个最大的或者最小的就完事了，和上一个状态没有关系。

所以贪心解决不了动态规划的问题。

对于动态规划问题，我将拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了！

• 确定dp数组（dp table）以及下标的含义
• 确定递推公式
• dp数组如何初始化
• 确定遍历顺序
• 举例推导dp数组

**因为一些情况是递推公式决定了dp数组要如何初始化！**所以要先求递推公式然后进行dp数组初始化

找问题的最好方式就是把dp数组打印出来，看看究竟是不是按照自己思路推导的！

做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。

然后再写代码，如果代码没通过就打印dp数组，看看是不是和自己预先推导的哪里不一样。

如果打印出来和自己预先模拟推导是一样的，那么就是自己的递归公式、初始化或者遍历顺序有问题了。

先思考问题：

• 这道题目我举例推导状态转移公式了么？
• 我打印dp数组的日志了么？
• 打印出来了dp数组和我想的一样么？

斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给你n ，请计算 F(n) 。

示例 1：
输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：输入：3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：
输入：4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3
提示：

0 <= n <= 30

【思路】

动规五步曲：

1. 确定dp数组以及下标的含义

   dp[i]的定义为：第i个数的斐波那契数值是dp[i]

2. 确定递推公式

   状态转移方程：dp[i] = dp[i-1] + dp[i-2];

3. dp数组如果初始化

   dp[0] = 0;
   dp[1] = 1;
   

4. 确定遍历顺序

   从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的

5. 举例推到dp数组

   按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导一下，当N为10的时候，dp数组应该是如下的数列：

   0 1 1 2 3 5 8 13 21 34 55

   如果代码写出来，发现结果不对，就把dp数组打印出来看看和我们推导的数列是不是一致的。

时间复杂度：O(n)
空间复杂度：O(n)
class Solution{
public：
    int fib(int N){
   	if(N <= 1) return N;
    vector<int> dp(N + 1);
    dp[0] = 0;
    dp[1] = 1;
    for(int i = 2; i <= N; i++){
        dp[i] = dp[i-1] + dp[i - 2];
    }
    return dp[N];
}
}

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：
输入：2
输出：2
解释：有两种方法可以爬到楼顶。

1 阶 + 1 阶
2 阶
示例 2：
输入：3
输出：3
解释：有三种方法可以爬到楼顶。

1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶
2 阶 + 1 阶

【思路】

本题大家如果没有接触过的话，会感觉比较难，多举几个例子，就可以发现其规律。

爬到第一层楼梯有一种方法，爬到二层楼梯有两种方法。

那么第一层楼梯再跨两步就到第三层 ，第二层楼梯再跨一步就到第三层。

所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来，那么就可以想到动态规划了。

我们来分析一下，动规五部曲：

1. 确定一个一维数组用来记录不同楼层状态

   dp[i]: 爬到第i阶楼梯，有dp[i]种方法

2. 确定递归公式

   因为每次可以跳1个或2个台阶所以有下面的操作

   首先是dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，那么再一步跳一个台阶不就是dp[i]了么。

   还有就是dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶不就是dp[i]了么。

   那么dp[i]就是 dp[i - 1]与dp[i - 2]之和！

   所以dp[i] = dp[i - 1] + dp[i - 2] 。

   在推导dp[i]的时候，一定要时刻想着dp[i]的定义，否则容易跑偏。

   这体现出确定dp数组以及下标的含义的重要性！

3. 确定dp数组如何初始化

   从dp数组定义的角度上来说，dp[0] = 0 也能说得通。

   需要注意的是：题目中说了n是一个正整数，题目根本就没说n有为0的情况。

   所以本题其实就不应该讨论dp[0]的初始化！

   我相信dp[1] = 1，dp[2] = 2，这个初始化大家应该都没有争议的。

4. 确定遍历顺序

   从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，遍历顺序一定是从前向后遍历的

5. 举例推到dp数组

   举例当n为5的时候，dp table（dp数组）应该是这样的

//时间复杂度：O(n)
//空间复杂度：O(n)
// 版本一
class Solution {
public:
    int climbStairs(int n) {
        if (n <= 1) return n; // 因为下面直接对dp[2]操作了，防止空指针
        vector<int> dp(n + 1);
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) { // 注意i是从3开始的
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

优化内存空间的方法

//时间复杂度：O(n)
//空间复杂度：O(1)
// 版本二
class Solution {
public:
    int climbStairs(int n) {
        if (n <= 1) return n;
        int dp[3];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            int sum = dp[1] + dp[2];
            dp[1] = dp[2];
            dp[2] = sum;
        }
        return dp[2];
    }
};

【修改题目】

每次可以爬1 、 2或者m 个台阶。问有多少种不同的方法可以爬到楼顶呢？

1阶，2阶，m阶就是物品，楼顶就是背包。

每一阶可以重复使用，例如跳了1阶，还可以继续跳1阶。

问跳到楼顶有几种方法其实就是问装满背包有几种方法。

动态规划五步曲：

1. 确定dp数组及下标含义

   dp[i]：爬到有i个台阶的楼顶，有dp[i]种方法。

2. 确定递推公式

   求装满背包有几种方法，递推公式一般都是dp[i] += dp[i - nums[j]];

   本题呢，dp[i]有几种来源，dp[i - 1]，dp[i - 2]，dp[i - 3] 等等，即：dp[i - j]

   那么递推公式为：dp[i] += dp[i - j]

3. dp数组如何初始化

   从递归公式出发dp[i] += dp[i-j],那么dp[0]一定为1，dp[0]是递归中一切数值的基础所在，如果dp[0]是0的话，其他数值都是0了。

   为什么这样设置是因为dp[i] 是由 dp[i-j]后面的推出的与本身没有关系，所以让dp[0]=1其余的为0即可

4. 确定遍历顺序

   这是背包里求排列问题，即：1、2步和2、1步都是三个台阶，但是这两种方法不同，所以需将target放在外循环，将nums放在内循环。

   每一步可以走多次，这是完全背包，内循环需要从前向后遍历。

5. 举例来推导dp数组

[C++代码]

//因为物品可以重复挑选所以式完全背包问题，所以有以下面两个求法，求组合与求排列

class Solution{
public:
    int climbStairs(int n){
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        for(int i = 1; i <= n; i++){//遍历容量
            for(int j = 1; j <= m; j){//遍历物品，可以用1步也可以用m步
                //dp[j] 由 dp[i-1],dp[i-2],....,dp[i-j]这些组成
            	dp[j] += dp[i - j]; 
            }
        }
        return dp[n];
    }
};

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

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

背包就是容量

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。

每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。

请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

示例 1：

输入：cost = [10, 15, 20] 输出：15 解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。

示例 2：

输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 输出：6 解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。

提示：

cost 的长度范围是 [2, 1000]。
cost[i] 将会是一个整型数据，范围为 [0, 999] 。

[思考]

注意题目描述：每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯

动态五步曲：

1. 确定dp数组以及下标含义：

   dp[i]的定义：第i个台阶所花费的最少体力为dp[i]

2. 确定递推公式

   可以有两个途径得到dp[i],一个是dp[i-1],一个是dp[i-2]

   dp[i] = min(dp[i-1], dp[i-2])+cost[i]

   注意这里为什么是加cost[i]，而不是cost[i-1],cost[i-2]之类的，因为题目中说了：每当你爬上一个阶梯你都要花费对应的体力值

3. dp数组如果初始化

   vector<int> dp(cost.size());
   dp[0] = cost[0];
   dp[1] = cost[1];
   

4. 确定遍历顺序

   因为是模拟台阶，而且dp[i]由dp[i-1]与dp[i-2]推出，所以是从前到后遍历cost数组就可以了。

5. 例举推到dp数组

   拿示例2：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ，来模拟一下dp数组的状态变化，如下：

   

时间复杂度：O(n)
空间复杂度：O(1)
// 版本一
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(cost.size());
        dp[0] = cost[0];
        dp[1] = cost[1];
        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]);//取倒数最少的
    }
};

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

 

示例 1:

输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
 

提示：

0 <= num < 2^31

【解题思路：】

根据如下图的思路，总结出”递推公式“（即转移方程）。因此，该题可以使用动态规划解决：

动态规划解析：

记数字num第i位数字位xi，数字num的位数为n；

例如：num = 12258的n=5，x1=1。

1. 确定dp数组的下标以及含义

   dp[i]代表以xi为结尾的数字翻译成字符串的方法最多有dp[i]个。

2. 确定状态转移方程：

   若xi和xi-1组成的两位数字可以被翻译，则dp[i] = dp[i-1] + dp[i-2];否则dp[i] = dp[i-1]。

   可以被翻译的两位数区间：当xi-1=0，组成的两位数是无法被翻译的（例如00，01，02，…）,因此区间位[10,25].

   [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-am5rmXKb-1626103523348)(C:\Users\mubao\AppData\Roaming\Typora\typora-user-images\image-20210524160738149.png)]

3. 初始化状态

   dp[0] = dp[1] = 1,即“无数组”和“第1位数字”的翻译方法数量均为1；

4. 确定遍历顺序

   因为dp[i]是由dp[i-1]与dp[i-2]确定，所以遍历顺序是从左向右。

**问题：**无数字情况dp[0]=1从何而来？

**答：**当num第1，2位的组成的数字属于[10,25]时，显然应有2中翻译方法，即dp[2]=dp[1]+dp[0]=2,而显然dp[1]=1,因此推出dp[0]=1.

1. 为了方便获取数字的各位xi，**考虑先将数字num转化为字符串s，（这种思想太重要了）**通过遍历s实现动态规划。

2. 通过字符串切片s[i-2:i]获取数字组合10*xi-1+xi,通过对比字符串ASCII判断字符串对应区间。

3. **空间使用优化：**由于dp[i]只与dp[i-1]有关，因此可使用两个变量ab分别记录dp[i],dp[i-1]，两个变量交替前进即可，此方法可省去dp列表使用的O(N)的额外空间。

4. 复杂度分析：

   • 时间复杂度：O(N),N为字符串s的长度（即数字num的位数log(num))，其确定了循环次数。
   • 空间复杂度：O(N),字符串s使用O(N)大小的额外空间

   

   时间复杂度：O(N)
   空间复杂度：O(N)因为创建了一个string s，字符串的空间是O(N)
   class Solution {
   public:
       int translateNum(int num) {
           string s = to_string(num);
           int a = 1, b = 1, len = s.size();
           for(int i = 2; i <= len; i++) {
               string tmp = s.substr(i - 2, 2);
               int c = tmp.compare("10") >= 0 && tmp.compare("25") <= 0 ? a + b : a;
               b = a;
               a = c;
           }
           return a;
       }
   };
   //优化空间：
   时间复杂度O(N):N为字符串s的长度，即数字num的位数log(num),其决定了循环次数
   空间复杂度O(1):几个变量使用常数大小的空间
   class Solution {
       public int translateNum(int num) {
           int a = 1, b = 1, x, y = num % 10;
           while(num > 9) {
               num /= 10;
               x = num % 10;
               int tmp = 10 * x + y;
               int c = (tmp >= 10 && tmp <= 25) ? a + b : a;
               b = a;
               a = c;
               y = x;
           }
           return a;
       }
   }
   

   //自己写的代码
   class Solution {
   public:
       int translateNum(int num) {
           string s = to_string(num);
           int len = s.size();
           vector<int> dp(len+1, 0);
           dp[1] = 1;
           dp[0] = 1;
           for(int i = 2; i <= len; i++)
           {
               //此时i-1对应s中的i，i-2对应s中的i-1这一点注意
               if((s[i-2] == '1' && (s[i-1] >= '0'  && s[i-1] <= '9')) || (s[i-2] == '2' && (s[i-1] >= '0' && s[i-1] <= '5')))
               {
                   dp[i] =  dp[i-2] + dp[i-1];
               }
               else
               {
                   dp[i] = dp[i-1];
               }
           }
           return dp[len];
       }
   };
   

   因为只用到了两个变量，所以没有必要创建一个N长度的数组，只需要创建两个变量a和b储存值就好了

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，“111” 可以将 “1” 中的每个 “1” 映射为 “A” ，从而得到 “AAA” ，或者可以将 “11” 和 “1”（分别为 “K” 和 “A” ）映射为 “KA” 。注意，“06” 不能映射为 “F” ，因为 “6” 和 “06” 不同。

给你一个只含数字的 非空 字符串 num ，请计算并返回 解码 方法的 总数 。

题目数据保证答案肯定是一个 32 位 的整数。

示例 1：

输入：s = “12”
输出：2
解释：它可以解码为 “AB”（1 2）或者 “L”（12）。
示例 2：

输入：s = “226”
输出：3
解释：它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。
示例 3：

输入：s = “0”
输出：0
解释：没有字符映射到以 0 开头的数字。含有 0 的有效映射是 ‘J’ -> “10” 和 ‘T’-> “20” 。由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。
示例 4：

输入：s = “06”
输出：0
解释：“06” 不能映射到 “F” ，因为字符串开头的 0 无法指向一个有效的字符。

提示：

1 <= s.length <= 100
s 只包含数字，并且可能包含前导零。

【思路】

本题主要的地方就是推导其动态方程，单独讨论“0”开头的情况

1. 首先当第一个字就是0时，我们直接返回0
2. 创建一个vector存储状态，size()+1可以使“10”这种情况不需要单独讨论
3. 初始化所有值为1，这样dp[0]与dp[1]就直接初始化了，所以我们可以从第二个字母开始

- 当当前数字为0前面不为1或2时直接return 0。这个比较好理解。
- 没有违规时前面肯定为1或者2，这个时候我们需要借用前面的数字来形成10和20，所以说前面那个数字所形成的
  状态无效，所以我们得取1或2前面的那个数字的状态，所以为：dp[i+1] = dp[i-1];

- 当前面数字为1时或者为2且当前数字小于7时，那么我们可以开始变换。
  这里的动态方程为：dp[i+1] = dp[i] + dp[i-1];
    - 示例 “1 2 1 2 3”， 它所对应的dp为：
    - dp “1 1 2 3 5 8” 你会发现其实每个数字所对应的状态为前两位的和.
- 当上述情况都不存在时证明此数字不会存在变换，所以直接取前面的状态。dp[i+1] = dp[i];
    - 示例 “1 2 1 7 9”， 它所对应的dp为：
    - dp “1 1 2 3 5 5” 注意9的状态没有发生变换，1 2 1 7为决定状态的数字

class Solution {
public:
    int numDecodings(string s) {
        if(s[0] == '0') return 0;
        //dp[i]对应的是从0到i-1的解码方法数
        vector<int> dp(s.size()+1, 1);
        
        for(int i = 1; i < s.size(); ++i)
        {
            //情况一：结尾为0，1234560
            if(s[i] == '0')
            {
                //结尾两位数代表大于26
                //因为英文字母就从1-26，大于26都不存在映射条件
                if(s[i-1] != '1' && s[i-1] != '2')
                    return 0;
                //结尾两数代表小于26
                //12110-》10只有一种映射所以不看只看121即dp[i+1] = dp[i-1]
                dp[i+1] = dp[i-1];
                //如果用break，输入数据"1201234"对用的输出为1预期结果为3输出错误-》但是为什么只能用continue而不能用break呢
                //这是因为break是跳出循环就不进行循环了，而continue需要跳出当前循环，要进行下一次循环
                continue;
            }
            //情况二结尾两位数的代表的编码方法不唯一 
			//12111->11有多种解码的方法所以dp[i+1] = dp[i] + dp[i-1]
            if(s[i-1] == '1' || (s[i-1] == '2' && s[i] < '7'))
                dp[i+1] = dp[i] + dp[i-1];
            //情况三：结尾两位数代表的解码方法唯一
            //12128//因为28只有一种解码方法所以28不增加解码方法，即dp[i+1] = dp[i];
            else
                dp[i+1] = dp[i];
        }
        return dp[s.size()];
    }
};

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Vchmnptv-1626103523351)(C:\Users\mubao\AppData\Roaming\Typora\typora-user-images\image-20210421102122772.png)]

class Solution {
public:
    bool check(string s){
        if(s[0] == '0') 
            return false;
        //将字符串转为数值用stoi，将数值转成字符串用to_string
        int n = stoi(s);
        return (n <= 26 && n >= 1);
    }
    int numDecodings(string s) {
        int n = s.length(), i;
        if(s[0] == '0') return 0;
        vector<int> dp(n+1, 1);
        for(i = 2; i <= n; i++){
            //flag1是两位数，flag2是一位数
            bool flag1 = check(s.substr(i-2, 2));
            bool flag2 = check(s.substr(i-1, 1));
            
            if(flag1 && flag2) 
                dp[i] = dp[i-2] + dp[i-1];
            else if(flag1) 
                dp[i] = dp[i-2];
            else if(flag2) 
                dp[i] = dp[i-1];
            else return 0;
        }
        return dp[n];
    }
};

[题目]
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

示例 1：

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示：

2 <= n <= 58

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。

示例 1: 输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。

【思路】

1. 确定dp数组以及下标的意义

   dp[i]: 拆分数子 i，可以得到的最大乘积为dp[i]

2. 确定递推公式

   对于正整数n，当n大于等于2时，可以拆分成至少两个正整数和。令k时拆分出的第一个正整数，则剩下的部分是n-k,n-k可以不继续拆分，或者可以继续拆分成至少两个正整数的和。

   当i大于等于2时，假设对正整数i拆分出的的第一个正整数是j(1<= j < i)，则有以下两种方案：

   • 将 i 拆分成 j 和 i - j 的和，且 i - j 不再拆分成多个正整数，此时乘积是 j * (i - j);
   • 将 i 拆分成 j 和 i - j 的和， 且 i - j 继续拆分成多个正整数，此时的乘积是 j * dp[i - j].

   因此当 j 固定时，有dp[i] = max( j * (i - j), j * dp[i - j] )由于 j 的取值范围是1 到 i - 1, 需要遍历所有的 j 得到dp[i]的最大值，因此可以得到转移方程如下：

   [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zojeq5lI-1626103523352)(C:\Users\mubao\AppData\Roaming\Typora\typora-user-images\image-20210414160748516.png)]

   递推公式：dp[i] = max(dp[i], max((i-j) * j, dp[i-j] * j));

3. dp的初始化

   有的题解里会给出dp[0] = 1，dp[1] = 1的初始化，但解释比较牵强，主要还是因为这么初始化可以把题目过了。

   严格从dp[i]的定义来说，dp[0] dp[1] 就不应该初始化，也就是没有意义的数值。

   拆分0和拆分1的最大乘积是多少？

   这是无解的。

   这里我只初始化dp[2] = 1，从dp[i]的定义来说，拆分数字2，得到的最大乘积是1，这个没有任何异议！

4. 确定遍历顺序

   确定遍历顺序，先来看看递归公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));

   dp[i] 是依靠 dp[i - j]的状态，所以遍历i一定是从前向后遍历，先有dp[i - j]再有dp[i]。

   枚举j的时候，是从1开始的。i是从3开始，这样dp[i - j]就是dp[2]正好可以通过我们初始化的数值求出来。

   j是从1开始遍历，拆分j的情况，在遍历j的过程中其实都计算过了。

   for(int i = 3; i <= n; i++)
       //i-j > 1，因为dp[1]无解，没有办法拆分
   	for(int j = 1; j < i - 1; j++){
           //为什么会有dp[i],是因为j是不断的变换，所以要保存i=6的dp值
   		dp[i] = max(dp[i], max((i-j) * j, dp[i-j] * j));
   	}
   }
   

5. 举例推导dp数组

//当n不小于2不大于58时可以使用动态规划
class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1);
        dp[2] = 1;
        for (int i = 3; i <= n ; i++) {
            for (int j = 1; j < i - 1; j++) {
                dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
            }
        }
        return dp[n];
    }
};

//如果n大于120时，此时使用动态规划的递推公式dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j))会报错，因为越界
class Solution {
public:
    int cuttingRope(int n) {
        if(n < 2)
        {
            return 0;
        }
        else if(n == 2)
        {
            return 1;
        }
        else if(n == 3)
        {
            return 2;
        }

        long result = 1;
        //当n>=5时，3(n-3) >= 2(n-2)
        while( n > 4)
        {
            result = result * 3 % 1000000007;
            n = n -3;
        }
        result = result *  n % 1000000007;
        return result;
    }
};

给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

【思路】

n为1的时候有一棵树，n为2有两棵树，这个是很直观的。

当3为头结点的时候，其左子树有两个节点，看这两个节点的布局，是不是和n为2的时候两棵树的布局也是一样的啊！

当2位头结点的时候，其左右子树都只有一个节点，布局是不是和n为1的时候只有一棵树的布局也是一样的啊！

发现到这里，其实我们就找到的重叠子问题了，其实也就是发现可以通过dp[1] 和 dp[2] 来推导出来dp[3]的某种方式。

dp[3]，就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量

元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量

元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量

元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量

有2个元素的搜索树数量就是dp[2]。

有1个元素的搜索树数量就是dp[1]。

有0个元素的搜索树数量就是dp[0]。

所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]

动态五步曲

1. 确定dp数组以及下标的意义

   dp[i]: 1到i为节点组成的二叉搜索树的个数为dp[i]

2. 确定递推公式

   *dp[i] += dp[以j为头结点左子树节点数量]dp[以j为头结点右子树节点的数量]

   j相当于头结点的元素，从1遍历到i为止

   dp[i] += dp[j-1] * dp[i-j];

   j-1为j为头结点左子树节点的数量，i-j为以j为头结点右子树节点的数量。

3. dp数组如何初始化

   初始化，只需要初始化dp[0]就可以了，推导的基础，都是dp[0]。

   ，空节点也是一颗二叉树，也是一颗二叉搜索树，这是可以说得通的。

   从递归公式上来讲，dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量] 中以j为头结点左子树节点数量为0，也需要dp[以j为头结点左子树节点数量] = 1， 否则乘法的结果就都变成0了。

   dp[0] = 1

4. 确定遍历顺序

   从递推公式可以看出，节点数为i的状态时依靠i之前节点数的状态，那么遍历i里面每一个数作为头结点的状态用j来遍历。

   for(int i = 1; i <= n; i++){
   	fro(int j = 1; j <= i; j++)
           //因为头结点是[1.....i]所有当以中间值j为头结点时，左子树的个数时j-1,右子树的个数时[i-j]
   		dp[i] += dp[j - 1] * dp[i - j]
   }
   

5. 举例推导dp 数组

   

我这里列到了n为5的情况，是为了方便大家 debug代码的时候，把dp数组打出来，看看哪里有问题。

class Solution {
public:
    int numTrees(int n) {
        //dp[i]:从0到i不同头结点元素组成二叉搜索树的个数为dp[i]
        vector<int>dp(n+1,0);
        dp[0] = 1;
        //第一个for循环遍历头结点个数
        for(int i = 1; i <= n; i++){
            //遍历不同头结点的个数
            for(int j = 1; j <= i; j++){
                dp[i] += dp[j-1] * dp[i-j];
               // cout<<"dp["<<i<<"] = "<<dp[i]<<endl;
            }
        }
        return dp[n];

    }
};

【题目】

把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
示例 1:
输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
示例 2:
输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]
 
1 <= n <= 11

【方法一：暴力法】超时

给定n个骰子，可得：

• 每个骰子摇到1至6的概率相等，都为1/6.
• 将每个骰子的点数看作独立情况，共右6^n种点数组合。例如n=2时点数的组合为：(1,1),(1,2),…,（2,1),…,(6,1),…,(6,6)
• n个骰子点数和的范围为[n, 6n]，数量为6n-n+1=5n+1

暴力统计：每个点数组合都对应一个点数和，考虑遍历所有点数组合，统计每个点数和的出现次数，最后除以点数组合的总数(除以6^n)，即可得到每个点数和出现的概率

如下图时，输入n=2时，点数组合，点数和，个点数概率的计算过程

暴力法需要遍历所有点数组合，因此时间复杂度为O(6^n)，观察本题输入取值范围1 <= n <= 11,可知此复杂度时无法接受的。

方法二：动态规划

输入n个骰子的解(即概率列表)为f(n),其中点数和x的概率为f(n,x)

假设已知n-1个骰子的解f(n-1),此时添加一枚骰子，求n个骰子的点数和为x的概率f(n,x)。

当添加骰子的点数为1时，前n-1个骰子的点数和应为x-1，方可组成点数和x；同理，当此骰子为2时，前n-1个骰子应为x-2；以此类推，直至此骰子点数为6。将这6种情况的概率相加，即可得到概率f(n,x).递推公式如下所示：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NGoey2Q2-1626103523357)(C:\Users\mubao\AppData\Roaming\Typora\typora-user-images\image-20210531164358320.png)]

根据以上分析，可知通过子问题的解f(n-1)可递推计算出f(n),而输入一个骰子的解f(1)已知，因此可通过解f(1)依此递推出任意解f(n)。

观察可发现，以上递推公式虽然可行，但是f(n-1, x- i)中的x-i会有越界的问题。例如**，希望递推计算f(2,2),由于骰子的点数范围为[1,6],因此直营求和f(1,1),即f(1,0),f(1,-1),f(1,-2)…等均无意义。**此越界问题导致代码编写困难

解决办法：将递推公式“逆向”改为“正向”递推

具体来看，由于新增骰子点数只可能为1-6，因此概率f(n-1, x)仅与f(n,x+1),f(n, x+2),…,f(n,x+6)相关。

因而，遍历f(n-1)中各点数和的概率，并将其相加至f(n)中所有相关项，即可完成f(n-1)至f(n)的递推。

将f(i)记为动态规划列表dp[i]，则i=1,....n的状态转移过程如下图所示
时间复杂度(O^2):状态转移循环n-1轮；每轮中当i=1，2，。。。n时，对应循环数量分别为6*6，11*6,....,[5(n-1)+1]*6;因此总体复杂度为O(n-1) * (6+[5*(n-1)+1])/2 * 6,即等价于O(N*N)
空间复杂度O(n):状态转移过程中，辅助数组tmp最大长度 为6(n-1)-[(n-1)-1]=5n-4,因此使用O(5n-4)=O(n)大小的额外空间

【代码】

通常做法是声明一个二维数组dp,dp[i] [j]代表前i各骰子的点数和j的概率，并执行状态转移，而由于dp[i] 仅由dp[i-1]递推得出，为了降低空间复杂度，只建立两个一维数组dp，tmp交替前进即可。

class Solution {
public:
    vector<double> dicesProbability(int n) {
        vector<double> dp(6, 1.0 / 6.0);
        //遍历骰子个数，因为一个骰子就已经赋值完了，所以从第2个骰子开始赋值
        for (int i = 2; i <= n; i++) {
            vector<double> tmp(5 * i + 1, 0);
            for (int j = 0; j < dp.size(); j++) {
                for (int k = 0; k < 6; k++) {
                    tmp[j + k] += dp[j] / 6.0;
                }
            }
            dp = tmp;
        }
        return dp;
    }

给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。

丑数 就是只包含质因数 2、3 和/或 5 的正整数。

示例 1：

输入：n = 6
输出：true
解释：6 = 2 × 3
示例 2：

输入：n = 8
输出：true
解释：8 = 2 × 2 × 2
示例 3：

输入：n = 14
输出：false
解释：14 不是丑数，因为它包含了另外一个质因数 7 。
示例 4：

输入：n = 1
输出：true
解释：1 通常被视为丑数。

提示：

-2^31 <= n <= 2^31 - 1

class Solution {
public:
    bool isUgly(int num) {
        if (num == 0) return false; // 特别判断
        while (true) {
            if (num == 1) return true; // 当num等于1时，代表这个数的质因数只包含2,3,5。那么为true
            if (num % 2 == 0) num /= 2; // 如果num中含有2的质因数，那么把它抽出来
            else if (num % 3 == 0) num /= 3; // 如果num中含有3的质因数，那么把它抽出来
            else if (num % 5 == 0) num /= 5; // 如果num中含有5的质因数，那么把它抽出来
            else return false; // 不是丑数，返回false
        }
    }
};

【方法二：动态规划】

丑数的递推性质：丑数只包含因子2，3，5，因此有“丑数 = 某较小丑数 * 某因子”

设一直长度为n的丑数序列x1，x2…，xn，求第n+1个丑数xn+1。根据递推性质，丑数xn+1只可能是以下三种情况（索引a，b，c为位置数）：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ExNhBZzd-1626103523367)(C:\Users\mubao\AppData\Roaming\Typora\typora-user-images\image-20210524223307068.png)]

因此，可设置指针a,b,c指向首个丑数（即1），循环根据递归公式得到下一个丑数，并每轮将对应指针执行加1即可

1. 确定dp数组下标及含义

   dp[i]:代表第i+1个丑数

2. 确定转移方程

   • 当索引a,b,c满足以下条件是，dp[i]为三种情况的最小值；

   • 每轮计算dp[i]后，需要更新索引a,b,c的值，时期始终满足方程条件。实现方法：独立判断dp[i]和dp[a] * 2,dp[b] * 3,dp[c] * 5的大小关系，若相等则将对应索引a,b,c加1；

     [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jRVSDRXH-1626103523368)(C:\Users\mubao\AppData\Roaming\Typora\typora-user-images\image-20210524223716291.png)]

3. 确定初始状态

   dp[0] = 1,即第一个丑数是1

4. 确定遍历顺序

   从小到大遍历

复杂度分析：

• **时间复杂度O(N)😗*其中N=n，动态规划需要遍历计算dp列表
• **空间复杂度O(N)😗*长度为N的dp列表使用O(N)的额外空间

class Solution {
public:
    int nthUglyNumber(int n) {
        int index_two = 0, index_three = 0, index_five = 0;
        vector<int> dp(n,1);
        for(int i = 1; i < n; i++)
        {
            dp[i] = min(dp[index_two] * 2, min(dp[index_three] * 3, dp[index_five] * 5));
            //注意下面不能用ifelseifelse
            //如果有else会导致重复的数会进来 1 2 3 4 5 6 6 7 8 9 10 10
            if(dp[i] == dp[index_two] * 2) index_two++;
            if(dp[i] == dp[index_three] * 3) index_three++;
            if(dp[i] == dp[index_five] * 5) index_five++;
        }
        return dp[n-1];
    }
};

编写一个程序，找出第 n 个丑数。

丑数就是质因数只包含 2, 3, 5 的正整数。

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:

1 是丑数。
n 不超过1690。

当n等于1370时，就超时了。

class Solution {
    bool isUglyNumber(int n){
        if(n <= 0)
            return false;
        while(n)
        {
            if(n == 1) return true;
            else if(n % 2 == 0) n /= 2;
            else if(n % 3 == 0) n /= 3;
            else if(n % 5 == 0) n /= 5;
            else
                return false;
        }
        return false;
    }
public:
    int nthUglyNumber(int n) {
        int number = 0;
        while(n)
        {
            number++;
            if(isUglyNumber(number))
            {
                n--;
            }
        }
        return number;
    }
};

【正解】

class Solution {
public:
    int nthUglyNumber(int n) {
       vector<int> nums;    //用于存放丑数
       nums.push_back(1);
       int i2 = 0, i3 = 0, i5 = 0;
       //这里的主逻辑就是丑数，从小到大不断增加，知道找到第n个丑数
       for(int i = 1; i < n; i++)   //因为i=0时，nums[i]就是1
       {
           int uglyNumber = min({nums[i2] * 2, nums[i3] * 3, nums[i5] * 5});//选取最小丑数
           nums.push_back(uglyNumber);
           if(nums[i2] * 2 == nums[i]) i2++;//上面uglyNumber，对应的下标要相应增加
           if(nums[i3] * 3 == nums[i]) i3++;
           if(nums[i5] * 5 == nums[i]) i5++;
       }
       return nums[n-1];
    }
};

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？
输入：m = 3, n = 7
输出：28

示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。

向右 -> 向右 -> 向下
向右 -> 向下 -> 向右
向下 -> 向右 -> 向右
示例 3：
输入：m = 7, n = 3
输出：28

示例 4：
输入：m = 3, n = 3
输出：6
提示：

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10^9

【方法一：深度优先遍历】

这道题目，刚一看最直观的想法就是用图论里的深搜，来枚举出来有多少种路径。

注意题目中说机器人每次只能向下或者向右移动一步，那么其实机器人走过的路径可以抽象为一颗二叉树，而叶子节点就是终点！

如图举例：

class Solution {
private:
    int dfs(int i, int j, int m, int n) {
        if (i > m || j > n) return 0; // 越界了
        if (i == m && j == n) return 1; // 找到一种方法，相当于找到了叶子节点
        return dfs(i + 1, j, m, n) + dfs(i, j + 1, m, n);
    }
public:
    int uniquePaths(int m, int n) {
        return dfs(1, 1, m, n);
    }
};

来分析一下时间复杂度，这个深搜的算法，其实就是要遍历整个二叉树。

这颗树的深度其实就是m+n-1（深度按从1开始计算）。

那二叉树的节点个数就是 2^(m + n - 1) - 1。可以理解深搜的算法就是遍历了整个满二叉树（其实没有遍历整个满二叉树，只是近似而已）

所以上面深搜代码的时间复杂度为O(2^(m + n - 1) - 1)，可以看出，这是指数级别的时间复杂度，是非常大的。

【方法二：动态规划】

已知：

机器人从（0,0)位置出发，到(m-1,n-1)终点

按照动规五步曲来说

1. 确定dp数组以及下标的含义

   dp[i] [j]:表示从（0，0）出发，到（i,j)有dp[i] [j]条不同的路径

2. 确定递推公式

   想要求dp[i] [j]，只能有两个方向来推导出来，即dp[i-1] [j]和dp[i] [j-1].

   那么显然，dp[i] [j] = dp[i-1] [j] + dp[i] [j-1],因为dp[i] [j]只有这两个方向过来

3. dp数组的初始化

   首先dp[i] [0]一定都是1，因为从(0, 0)的位置到(i, 0)的路径只有一条，那么dp[0] [j]也同理。

   for(int i = 0; i < m; i++)dp[i][0] = 1;
   for(int j = 0; j < n; j++)dp[0][j] = 1
   

4. 确定遍历顺序

   这里要看一下递归公式dp[i] [j] = dp[i - 1] [j] + dp[i] [j - 1]，dp[i] [j]都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以了。

   这样就可以保证推导dp[i] [j]的时候，dp[i - 1] [j] 和 dp[i] [j - 1]一定是有数值的。

5. 例举推到dp数组

   

//时间复杂度：O(m*n)
//空间复杂度：O(m*n)
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for (int i = 0; i < m; i++) dp[i][0] = 1;
        for (int j = 0; j < n; j++) dp[0][j] = 1;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
};

优化空间

//时间复杂度：O(m*n)
//空间复杂度：O(n)
Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> dp(n);
        for (int i = 0; i < n; i++) dp[i] = 1;
        for (int j = 1; j < m; j++) {
            for (int i = 1; i < n; i++) {
                dp[i] += dp[i - 1];
            }
        }
        return dp[n - 1];
    }
};

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格种的障碍物和空位置分别用1和0表示

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：

1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

• m == obstacleGrid.length
• n == obstacleGrid[i].length
• 1 <= m, n <= 100
• obstacleGrid[i][j] 为 0 或 1

动态规划五步曲：

1. 确定dp数组以及下标含义

   dp[i] [j]: 表示从(0,0)出发，到(i,j)有dp[i] [j]条不同的路径

2. 确定递推公式

   递推公式与62题一样，dp[i] [j] = dp[i - 1] [j] + dp[i] [j - 1]，但是注意的是，以为有障碍(i , j)如果就是障碍的话就应该保持状态（初始状态为0）

   if (obstacleGrid[i][j] == 0) { // 当(i, j)没有障碍的时候，再推导dp[i][j]
       dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
   }
   

3. dp数组如何初始化

   vector<vector<int>> dp(m, vector<int>(n,0));
   for(int i = 0; i < m && obstacleGrid[i][0]; i++)dp[i][0] = 1;
   for(int j = 0; j < n && obstacleGrid[0][j]; j++)dp[0][j] = 1;
   
   

   但如果(i, 0) 这条边有了障碍之后，障碍之后（包括障碍）都是走不到的位置了，所以障碍之后的dp[i] [0]应该还是初始值0。

   

4. 确定遍历顺序

   从递归公式dp[i] [j] = dp[i-1] [j] + dp[i] [j-1]中可以看出，一定是从左到右一层一层的遍历，这样保证推导dp[i] [j]的时候， dp[i-1] [j] 和 dp[i] [j-1]一定是有数值

   for(int i = 1; i < m; i++){
       for(int j = 1; j < n; j++){
           //如果碰到障碍保持原状
           if(obstacleGrid[i][j] == 1)
               continue;
           dp[i][j] = dp[i-1][j] + dp[i][j-1];
       }
   }
   

5. 举例推导dp数组

   

//时间复杂度：O(n*m)n,m分别为obstacleGrid的长度与宽度
//空间复杂度：O(n*m)
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        //m为网格的行数，n为网格的列数
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        //初始化的时候要注意，将由障碍物的地方绕过去
        for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
        for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;
        //相比较上一题：
        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];
    }
};

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

输入：grid = [[1,2,3],[4,5,6]]
输出：12

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i] [j] <= 100

路径问题动规五部曲分析如下：

1. 确定dp数组（dp table）以及下标的含义

   dp[i] [j]：从[0,0]出发到[i] [j]的最小路径的和

2. 确定递推公式

   由于每一步只能向下或向右移动**，因此想要走到位置(i, j)，上一步就只能在位置(i-1，j)或者位置(i, j-1)中的最小值位置**。

   dp[i] [j] = min(dp[i-1] [j], dp[i] [j-1]) + grid[i] [j];

   应当注意的=是只有一列或一行的情况，

   情况一：只有一列

   dp[0] [j] = dp[0] [j-1] + grid[0] [j];

   情况二：只有一行，这一种情况要单独考虑

   dp[0] [j] = dp[0] [j-1] + grid[0] [j];

3. dp数组如何初始化

   从递推公式dp[i] [j] = min(dp[i-1] [j], dp[i] [j-1]) + grid[i] [j];可以看出，递推公式的基础就是dp(0,0)

   dp[0] [0] = grid[0] [0];

    //初始化数组
           int row = grid.size();
           int col = grid[0].size();
           //dp[i][j]：从[0,0]出发到[i][j]的最小路径的和
           vector<vector<int>> dp(row, vector<int>(col, 0));
           dp[0][0] = grid[0][0];
   
   

4. 确定遍历顺序

   由递推公式dp[i] [j] = min(dp[i-1] [j], dp[i] [j-1]) + grid[i] [j];可知遍历的顺序是从前向后遍历的所以有

           //先遍历行，再遍历列
           for(int i = 1; i < row; i++){
               //只有一行或一列的情况要单独考虑
               dp[i][0] = dp[i-1][0] + grid[i][0];
               for(int j = 1; j < col; j++){
                   dp[0][j] = dp[0][j-1] + grid[0][j];
                   dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
                   //cout<<dp[i][j]<<" ";
               }
   

5. 例举dp矩阵

   要深知dp矩阵的每一行每一列代表的含义是什么

   //异常处理只有一行时,怎么讲它放入下面循环中呢？
           if(row == 1)
           {
               for(int j = 1; j < col; j++)
                   dp[0][j] = dp[0][j-1] + grid[0][j];
           }
   

   上面的代码是最容易遗漏的，因为只有一行数据时时不能进入下面的循环

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        //初始化数组
        int row = grid.size();
        int col = grid[0].size();
        //dp[i][j]：从[0,0]出发到[i][j]的最小路径的和
        vector<vector<int>> dp(row, vector<int>(col, 0));
        dp[0][0] = grid[0][0];

        //同一处理初始化
		if(row > 0)//如果有行
        {
             for(int i = 1; i < row; i++)
            {
                dp[i][0] = dp[i-1][0] + grid[i][0];
            }
		}
       
        if(col > 0)//如果有列
        {
            for(int j = 1; j < col; j++)
            {
                dp[0][j] = dp[0][j-1] + grid[0][j];
            }
        }
       
		 //下面的代码是行数大于1列数大于1是才走
        //先遍历行，再遍历列
        for(int i = 1; i < row; i++){
            for(int j = 1; j < col; j++){
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
                //cout<<dp[i][j]<<" ";
            }
        }
        return dp[row-1][col-1];
    }
};

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1：

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
2
3 4
6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
示例 2：

输入：triangle = [[-10]]
输出：-10

提示：

1 <= triangle.length <= 200
triangle[0].length == 1
triangle[i].length == triangle[i - 1].length + 1
-10^4 <= triangle[i] [j] <= 10^4
进阶：
你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？

路径问题动规五部曲分析如下：

1. 确定dp数组（dp table）以及下标的含义

   dp[i] [j]：表示从三角形走到位置(i,j)的最小路径和。这里的位置(i,j)指的是三角形中第i行第j列的位置（从零开始）

2. 确定递推公式

   由于每一步只能移动到下一行相邻节点上**，因此想要走到位置(i, j)，上一步就只能再位置(i-1，j-1)或者位置(i-1, j)**。

   dp(i, j) = min(dp(i-1, j-1), dp(i-1, j))+c(i, j);

   注意当j=0或者当j=i时，上述的方程有一些项是没有意义的。当j=0时，f(i-1, j-1)没有意义,当j=i时，f(i-1, j)没有意义

   dp(i, 0) = dp(i-1, 0) + c(i , 0); dp(i，i） = dp(i-1, i-1) + c(i, i);

   最后答案时dp(n-1, 0)到dp(n-1, n-1)中的最小值，其中n时三角形的行数

3. dp数组如何初始化

   从递推公式**dp(i, j) = min(dp(i-1, j-1), dp(i-1, j))+c(i, j);可以看出，递推公式的基础就是dp(0,0)

   dp[0] [0] = triangle[0] [0]

vector<vector<int>> dp(triangle.size(),vector<int>(triangle[trangle.size()].size());
dp[0][0] = triangle[0][0];

4. 确定遍历顺序

   dp[i] [j] 是根据dp[i - 1] [j-1] 和 dp[i - 1] [j] 推导出来的，那么一定是从前到后遍历！

  for (int i = 1; i < len; i++) {
            //情况一：
            dp[i][0] = dp[i-1][0] + triangle[i][0];
            //情况三：
            for(int j = 1; j < i; j++){
                dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
            }
            //情况二：
            //为什么放在这个位置，因为第一层是dp[1][1];第2层是dp[2][2].....
            dp[i][i] = dp[i-1][i-1] + triangle[i][i];
        }

5. 举例推导dp数组

[错误的代码]

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        
        //初始化dp数组
        //dp[i]：代表从到第i层最小路径的和
        int total_leve = triangle.size();
        vector<int> dp(total_leve, INT_MAX);
        dp[0] = triangle[0][0];
        int result = INT_MAX;

        for(int i = 1; i < total_leve; i++){
            for(int j = 0; j <= i; j++){
               // result =  min(result, dp[i-1]+triangle[i][j]);
                dp[i] =  min(dp[i], dp[i-1]+triangle[i][j]);
            //    cout<<dp[i]<<"   ";
            }
        }
        return dp[total_leve-1];
    }
};

【参考代码】

min_element和max_element的用法;范围是左闭右开
#include<algorithm>
作用：查数组中的最大值，返回容器中最小值和最大值的指针。当想获取值的时候要解引用

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int row = triangle.size();
        int col = triangle[row-1].size();
        vector<vector<int>> dp(row,vector<int>(col, 0) );
        if(row == 0 || col == 0)
            return -1;
        //初始化数组
        dp[0][0] = triangle[0][0];
        //初始化数组边界
        if(row > 0)//如果存在行
       { for(int i = 1; i < row; i++)
        {
            dp[i][0] = dp[i-1][0] + triangle[i][0];
        }
        }
        if(col >0)//如果存在列
        {
            for(int j = 1; j < col; j++)
            {
                dp[j][j] = dp [j-1][j-1] + triangle[j][j];
            }
        }
        
        
        for(int i = 1; i < row; i++)
        {
            for(int j = 1; j < i; j++)
            {
                dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j];
            }
        }
        return *min_element(dp[row-1].begin(), dp[row-1].end());
    }
};

【题目】

有一个长度为 arrLen 的数组，开始有一个指针在索引 0 处。

每一步操作中，你可以将指针向左或向右移动 1 步，或者停在原地（指针不能被移动到数组范围外）。

给你两个整数 steps 和 arrLen ，请你计算并返回：在恰好执行 steps 次操作以后，指针仍然指向索引 0 处的方案数。

由于答案可能会很大，请返回方案数 模 10^9 + 7 后的结果。

 

示例 1：

输入：steps = 3, arrLen = 2
输出：4
解释：3 步后，总共有 4 种不同的方法可以停在索引 0 处。
向右，向左，不动
不动，向右，向左
向右，不动，向左
不动，不动，不动
示例  2：

输入：steps = 2, arrLen = 4
输出：2
解释：2 步后，总共有 2 种不同的方法可以停在索引 0 处。
向右，向左
不动，不动
示例 3：

输入：steps = 4, arrLen = 2
输出：8
 

提示：

1 <= steps <= 500

【分析】

用dp[i] [j]表示在 i 步操作后，指针位于下标 j 的方案数。其中，i的取值范围是0 <= i <= steps, j的取值范围是0 <= j <= arrLen - 1;

由于一共执行steps步操作，因此指针所在下标一定不会超过steps，可以将j的取值范围进一步缩小到 0 <= j <= min(arrLen - 1, teps)。

当没有进行任何操作时，指针一定位于下标0，因此动态规划的初始条件为dp[0] [0] = 1，当1 <= j <= min(arrLen - 1, steps)时有dp[0 ] [j] = 0;

每一步操作中，指针都可以向左或者向右移动1步或者停在原地。因此，当1<=i<=steps时，状态dp[i] [j]可以从dp[i-1] [j-1] 、dp[i-1] [j]、 dp[i-1] [ j+1]

初始化，注意边界，当j = 0时，dp[i-1] [j-1] = 0;当 j = min(arrLen - 1, steps)时，dp[i-1] [j+1] = 0。最左边界不能向左移动，最右边界不能向右移动。

注意：题目要求需要对每个状态计算值对10^9+7取模，最终结果得到dp[steps] [0]的值即为答案。

class Solution {
    const int MOD = 1000000007;
public:
    int numWays(int steps, int arrLen) {
        if(arrLen == 1)
            return 1;
        //指针移动的最远距离，要么是数组的边界要么是移动的步数,取最小
        int MaxColumn = min(steps, arrLen - 1);
        //dp[i][j]:表示第i步操作后，指针位于下标j的方案数。
        vector<vector<int>> dp(steps + 1, vector<int>(MaxColumn + 1, 0));
        dp[0][0] = 1;
        for(int i = 1; i <= steps; i++)
        {
            for(int j = 0; j <= MaxColumn; j++)
            {
                /*
                下面的写法同样会产生数组越界j = 0时怎么会有[j-1]存在
                //最左边边界不能向左移
                if(j == 0)
                    dp[i-1][j-1] = 0;
                //最右边界不能向右移
                if(j == MaxColumn)
                    dp[i-1][j+1] = 0
                */
                
                //题目要求说要防止加法越界，对计算值进行取模处理，所以每次进行加法操作时都需要对加法值进行取模
                //（为什么该题不能像120题那样割裂开是因为，dp[i][j]不仅与上一值dp[i-1][j]有关还与dp[i-1][j+1]有关，如果割裂开dp[i-1][j+1]一直为0）
                if(j-1 < 0)
                {
                    //最左边界情况
                    dp[i][j] = (dp[i-1][j]  + dp[i-1][j+1] )% MOD;
                }
                else if(j+1 > MaxColumn)
                {
                    //最右边界情况
                    dp[i][j] = (dp[i-1][j]   + dp[i-1][j-1])% MOD ;
                }
                else
                {
                    //处于最左与最右之间
                    dp[i][j] = (((dp[i-1][j]  + dp[i-1][j-1])%MOD  + dp[i-1][j+1]) % MOD);
                }
            }
        }
        //返回第steps步下标为0的dp值
        return dp[steps][0];
    }
};

【题目】

集团里有 n 名员工，他们可以完成各种各样的工作创造利润。
第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与。如果成员参与了其中一项工作，就不能参与另一项工作。
工作的任何至少产生 minProfit 利润的子集称为 盈利计划 。并且工作的成员总数最多为 n 。
有多少种计划可以选择？因为答案很大，所以 返回结果模 10^9 + 7 的值。
示例 1：

输入：n = 5, minProfit = 3, group = [2,2], profit = [2,3]
输出：2
解释：至少产生 3 的利润，该集团可以完成工作 0 和工作 1 ，或仅完成工作 1 。
总的来说，有两种计划。
示例 2：

输入：n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
输出：7
解释：至少产生 5 的利润，只要完成其中一种工作就行，所以该集团可以完成任何工作。
有 7 种可能的计划：(0)，(1)，(2)，(0,1)，(0,2)，(1,2)，以及 (0,1,2) 。

提示：
1 <= n <= 100
0 <= minProfit <= 100
1 <= group.length <= 100
1 <= group[i] <= 100
profit.length == group.length
0 <= profit[i] <= 100

有两个变量的约束，所以应该使用三维DP解决

【解题思路】

本题与经典背包问题十分相似，两者不同点在于经典背包问题只有一种容量限制，而本题却有两种限制：集团员工人数上限n,以及工作产生的利润下限minProfit

通过经典背包问题的练习，我们已经知道经典背包可以使用二维动态规划求解：两个维度分别代表物品和容量的限制标准。对于本题上述两种限制，我们可以想到使用三维动态规划求解。本题的三维分别为：当前可选择的工作，已选择的小组员工人数，以及目前状态的工作获利下限。

确定三维数组dp的动态规划状态，其中dp[i] [j] [k] 表示在前i个工作中选择了j个员工，并且满足工作利润至少为k的情况下的盈利总数目。假设group数组长度为len，那么在不考虑取模的运算情况下， 最终答案为：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7eFkTJ7j-1626103523376)(C:\Users\mubao\AppData\Roaming\Typora\typora-user-images\image-20210609092103766.png)]

所以我们可以新建一个三维数组dp[len+1] [n+1] [minProfit+1],初始化dp[0] [0] [0]=1。接下来分析状态转移方程，对于每个工作i，我们根据当前工作人数上限j，有能够开展当前工作和无法开展当前工作两种情况：

• 如果无法开展当前工作i，那么显然：dp[i] [j] [k] = dp[i-1] [j] [k]

• 如果能够开展当前工作i，设当前小组人数为group[i]，工作获利为profit[i]，那么不考虑取模运算的情况下有：

  dp[i] [j] [k] = dp[i-1] [j] [k] + dp[i-1] [j-group[i]] [max(0, k-profit[i])]

由于我们定义的第三维是工作利润至少为k而不是工作利润恰好为k，因此上述状态转移方程中右侧的第三维是max(0, k-profit[i])而不是k-profit[i]，因为k-profit[i]可能是负数

class Solution {
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        int len = group.size(), MOD = (int)1e9 + 7;
        vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(n + 1, vector<int>(minProfit + 1)));
        dp[0][0][0] = 1;
        for (int i = 1; i <= len; i++) {
            int members = group[i - 1], earn = profit[i - 1];
            for (int j = 0; j <= n; j++) {
                for (int k = 0; k <= minProfit; k++) {
                    if (j < members) {
                        dp[i][j][k] = dp[i - 1][j][k];
                    } else {
                        dp[i][j][k] = (dp[i - 1][j][k] + dp[i - 1][j - members][max(0, k - earn)]) % MOD;
                    }
                }
            }
        }
        int sum = 0;
        for (int j = 0; j <= n; j++) {
            sum = (sum + dp[len][j][minProfit]) % MOD;
        }
        return sum;
    }
};

可以发现dp[i] [j] [k] 仅与 dp[i-1] […] […]有关，所以本题可以用二维动态规划解决。当采用二维动态规划的解法时，对于最小工作利润为0的情况，无论当前在工作的员工有多少人，我们总能提供一种方案，所以初始化dp[i] [0] = 1。此外，降维后dp数组的遍历顺序改为逆序，因为这样才能保证求状态dp[j ] [k]时，用到的时dp[j-members] [max(0, k - earn)]是上一时刻值，而正序遍历则会改写该值。

class Solution {
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        vector<vector<int>> dp(n+1, vector<int>(minProfit+1));
        //最小利润为0的情况无论当前工作为多少人，我们总能提供一种方案，所以初始化dp[i][0]=1
        for(int i = 0; i <= n; i++)
        {
            dp[i][0] = 1;
        }
        int len = group.size(), MOD = 1e9 + 7;
        for(int i = 1; i <= len; i++)
        {
            int members = group[i-1], earn = profit[i-1];//因为i 属于 1~10包括10而group下标是0~9group[i-1]就是当下的员工数，profit[i-1]就是当下的利润
            for(int j = n; j >= members; j--)
            {
                for(int k = minProfit; k >= 0; k--)
                {
                    dp[j][k] = (dp[j][k] + dp[j-members][max(0, k - earn)]) % MOD;
                }
            }
        }
        return dp[n][minProfit];
    }
};

思考：为什么三维DP数组需要累加和而降维成二维就不需要进行累加呢？

复杂度分析：

• 时间复杂度：O(len * n * minProfit)，其中len为数组group的长度
• 空间复杂度：O(n * minProfit).使用空间优化的实现，需要创建n+1行minProfit+1列的二维数组dp

【题目】

此方案包含 target = 3 个街区，分别是 [{1}, {2,2}, {1,1}]。
涂色的总花费为 (1 + 1 + 1 + 1 + 5) = 9。
示例 2：

输入：houses = [0,2,1,2,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
输出：11
解释：有的房子已经被涂色了，在此基础上涂色方案为 [2,2,1,2,2]
此方案包含 target = 3 个街区，分别是 [{2,2}, {1}, {2,2}]。
给第一个和最后一个房子涂色的花费为 (10 + 1) = 11。
示例 3：

输入：houses = [0,0,0,0,0], cost = [[1,10],[10,1],[1,10],[10,1],[1,10]], m = 5, n = 2, target = 5
输出：5
示例 4：

输入：houses = [3,1,2,3], cost = [[1,1,1],[1,1,1],[1,1,1],[1,1,1]], m = 4, n = 3, target = 3
输出：-1
解释：房子已经被涂色并组成了 4 个街区，分别是 [{3},{1},{2},{3}] ，无法形成 target = 3 个街区。

提示：

m == houses.length == cost.length
n == cost[i].length
1 <= m <= 100
1 <= n <= 20
1 <= target <= m
0 <= houses[i] <= n
1 <= cost[i] [j] <= 10^4

【思路】

为什么要用三维的数组来存储已有的状态？

因为我们有三个数据需要存储：

1. 当前是第几个房子
2. 当前房子的颜色
3. 当前房子组成的街区数

dp数组和转移方程是什么？

dp[i] [j] [k]:表示前i个房子组成j个街区，并且第i个房子的颜色为k，此时的最小花费数据范围：房子i属于[0 , m-1],街区j属于[0, target],颜色k 属于[0, n];

状态方程：因为这个城市有的已经有颜色了，所以需要依据这个进行分类讨论

• 情况一：当前房子有颜色

  如果第i-1个房子与第i个房子颜色不同,则会形成新的街区

  如果第i-1个房子与第i个房子颜色相同，则街区数量不变

  如果此时房子已经有颜色，就不需要重新粉刷，没有cost的费用

  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ctT8yPIF-1626103523376)(C:\Users\mubao\AppData\Roaming\Typora\typora-user-images\image-20210504091526259.png)]

• 情况二：当前房子无颜色

  此时就要对当前房子进行涂色了，涂成不同的颜色就会有不同的费用，但转移方程还是类似的。注意到这里cur_color是一个范围值，因此需要对其进行循环遍历

  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6JUg294L-1626103523377)(C:\Users\mubao\AppData\Roaming\Typora\typora-user-images\image-20210504091747870.png)]

最终结果怎么取：

如何初始化：

因为取的是min，所以我们把dp的所有数全部初始化为最大数，**这个数可以进行运算但是不能溢出，**当最后取结果时还是这个大数，则说明没有方案能让这些房子形成target个街区。

class Solution {
public:
    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
        // dp[i][j][k]: 前i个房子组成j个街区，且第i个房子的颜色为k，此时的最小花费
        // 房子∈[0, m-1]，街区∈[0, target]，颜色∈[0, n]
        int dp[m][target+1][n+1];
        memset(dp, 0x3f3f3f3f, sizeof(dp));

        // 初始化
        if(houses[0] == 0) {
            for(int k = 1; k <= n; k++)
                dp[0][1][k] = cost[0][k-1];
        }
        else
            dp[0][1][houses[0]] = 0;
        
        // 转移
        for(int i = 1; i < m; i++) {
            // 房子本身无颜色
            if(houses[i] == 0) {
                for(int cur_color = 1; cur_color <= n; cur_color++) {
                    for(int prv_color = 1; prv_color <= n; prv_color++) {
                        for(int j = 1; j <= target; j++) {
                            if(cur_color == prv_color)
                                dp[i][j][cur_color] = min(dp[i][j][cur_color], dp[i-1][j][cur_color] + cost[i][cur_color-1]);
                            else
                                dp[i][j][cur_color] = min(dp[i][j][cur_color], dp[i-1][j-1][prv_color] + cost[i][cur_color-1]);
                        }
                    }
                }
            }
            // 房子本身有颜色
            else {
                int cur_color = houses[i];
                for(int prv_color = 1; prv_color <= n; prv_color++) {
                    for(int j = 1; j <= target; j++) {
                        if(cur_color == prv_color)
                            dp[i][j][cur_color] = min(dp[i][j][cur_color], dp[i-1][j][cur_color]);
                        else
                            dp[i][j][cur_color] = min(dp[i][j][cur_color], dp[i-1][j-1][prv_color]);
                    }
                }
            }
        }
        int ans = *min_element(dp[m-1][target], dp[m-1][target]+n+1);//min_element的作用范围是左闭右开，下标对用的值是0~n但是min_element后面参数到的位置是n+1
        return ans == 0x3f3f3f3f ? -1 : ans;
    }
};

如果这几种背包，分不清，我这里画了一个图，如下：

有N件物品和一个最多能背重量为W 的背包。第 i 件物品的重量是 weight[i] ，得到的价值是 value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

每一件物品其实只有**两个状态，**取或者不取，所以可以使用回溯法搜索出所有的情况，那么时间复杂度就是O(2^n)，这里的n表示物品数量。

举一个例子：

背包最大重量为4。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-OEPCqFa6-1626103523379)(C:\Users\mubao\AppData\Roaming\Typora\typora-user-images\image-20210309100638107.png)]

二维dp数组01背包

动态规划五步曲：

1. 确定dp数组以及下标的含义

   对于背包问题，有一种写法，是使用二维数组，即dp[i] [j]表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

要时刻记着这个dp数组的含义，下面的一些步骤都围绕这dp数组的含义进行的这里i代表什么，j代表什么。

2. 确定递推公式

   dp[i] [j]的含义：从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

   那么可以有两个方向推出来dp[i] [j]，

   • 由dp[i - 1] [j]推出，即背包容量为j，里面不放物品 i 的最大价值，此时dp[i] [j]就是dp[i - 1] [j]。
   • 由dp[i - 1] [j - weight[i]]推出，dp[i - 1] [j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1] [j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值

   所以递归公式：

   dp[i] [j] = max(dp[i - 1] [j], dp[i - 1] [j - weight[i]] + value[i]);

   解读上面的公式：
   dp[i][j]代表从物品0-i选取物品放进容量为j背包中价值总和最大是dp[i][j]
   可能是前0-i个物品选取放进容量为j的背包中的价值就是最大的，根本不需要放物品i。所以对于这种情况dp[i][j] = dp[i-1][j]背包的容量是j
   还有一种可能就是放第i个物品。此时需要背包容量为j-weight[i]的背包放如0-i-1个物品的价值要是最大，当放入物品i的时候达到最大的价值
   dp[i][j] = dp[i-1][j-weight[i]] + value[i];
   综上所述：dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]);
   

3. dp数组如何初始化

   关于初始化，一定要和dp数组的定义吻合，否则到递推公式的时候就会越来越乱。

   首先从 dp[i] [j] 的定义出发，如果背包容量 j 为 0 的话，即 dp[i] [0]，无论是选取哪些物品，背包价值总和一定为0。如图：

   

   状态转移方程 dp[i] [j] = max(dp[i - 1] [j], dp[i - 1] [j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。

dp[0] [j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。

// 倒叙遍历
for (int j = bagWeight; j >= weight[0]; j--) {
    dp[0][j] = dp[0][j - weight[0]] + value[0]; // 初始化i为0时候的情况
}

//你还不如这样赋值
for(int j = wiehgt[0]; j <= bagWeight; j++)//注意这里不能用j=0开始，因为如果j=0，根本不能容纳物品0的容量
{
    dp[0][j] = value[0];
}

[重要]大家应该发现，这个初始化为什么是倒叙的遍历的？正序遍历就不行么？

正序遍历还真就不行，dp[0] [j]表示容量为j的背包存放物品0时候的最大价值，物品0的价值就是15，因为题目中说了**每个物品只有一个！**所以dp[0] [j]如果不是初始值的话，就应该都是物品0的价值，也就是15。

// 正序遍历
for (int j = weight[0]; j <= bagWeight; j++) {
    dp[0][j] = dp[0][j - weight[0]] + value[0];
}

例如dp[0] [1] 是15，到了dp[0] [2] = dp[0] [2 - 1] + 15; 也就是dp[0] [2] = 30 了，那么就是物品0被重复放入了。

所以一定要倒叙遍历，保证物品0只被放入一次！这一点对01背包很重要，后面在讲解滚动数组的时候，还会用到倒叙遍历来保证物品使用一次！

此时dp数组初始化情况如图所示：

总之就是倒序遍历。

**dp[0] [j] 和 dp[i] [0] 都已经初始化了，**那么其他下标应该初始化多少呢？

dp[i] [j]在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了，因为0就是最小的了，不会影响取最大价值的结果。

**如果题目给的价值有负数，那么非0下标就要初始化为负无穷了。**例如：一个物品的价值是-2，但对应的位置依然初始化为0，那么取最大值的时候，就会取0而不是-2了，所以要初始化为负无穷。

这样才能让dp数组在递归公式的过程中取最大的价值，而不是被初始值覆盖了。

易错点：

• 初始化数组时，物品容量是从【0，bagWeight】,物品是从【0，物品数量-1】，而不是vector<vector< int >> dp(weight.size(), vector< int >(bagWeight, 0))

//初始化dp数组
vector<vector<int>> dp(weight.size() , vector<int>(bagWeight + 1, 0));
//因为创建数组初始化为0所以才能用倒叙
for(int j = baWeight; j >= weight[0]; j--){
    dp[0][j] = dp[0][j - weight[0]] + value[0];
}

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];//这是为了展现dp数组里元素的变化
        else
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i]);
    }
}

5. 举例推导dp数组

   

void test_2_wei_bag_problem1(){
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagWeight = 4;//背包的容量为4
    
    //二维数组
    //为什么将二维数组初始化为0，因为当一个背包什么都不放的时候最大价值为0。
    vector<vector<int>> dp(weight.size() + 1, vector<int>(bagWeight + 1, 0));
    
    //初始化
    for(int j = bagWeight; j >= weight[0]; j--){
        dp[0][j] = dp[0][j - weight[0]] + value[0];
    }
    
    //weight数组的大小就是物品个数
    //i是从1开始遍历的，而不是零这就是为什么建立dp数组的时候行数是weight.size+1,列数是bagWeight.size+1
    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]);
        }
    }
    cout << dp[weight.size()-1][bagWeight]<<endl;
}

int main(){
	test_2_wei_bag_problem1();
}

今天我们就来说一说滚动数组，其实在前面的题目中我们已经用到过滚动数组了，就是把二维dp降为一维dp，一些录友当时还表示比较困惑。

那么我们通过01背包，来彻底讲一讲滚动数组！

接下来还是用如下这个例子来进行讲解

背包最大重量为4。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Z6Raju2l-1626103523382)(C:\Users\mubao\AppData\Roaming\Typora\typora-user-images\image-20210309110503153.png)]

在使用二维数组的时候，递推公式：dp[i] [j] = max(dp[i - 1] [j], dp[i - 1] [j - weight[i]] + value[i]);

其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i] [j] = max(dp[i] [j], dp[i] [j - weight[i]] + value[i]);

于其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了，只用dp[j]（一维数组，也可以理解是一个滚动数组）。

这就是滚动数组的由来，需要满足的条件是上一层可以重复利用，直接拷贝到当前层。

读到这里估计大家都忘了 dp[i] [j]里的 i 和 j 表达的是什么了，i 是物品，j 是背包容量。

dp[i] [j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

一定要时刻记住这里i和j的含义，要不然很容易看懵了。

动态规划五步曲分析：

1. 确定dp数组的定义

   在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j].

2. 一维dp数组的递推公式

   dp[j]为容量为j的背包所背的最大价值，那么如何推导dp[j]呢？

   dp[j]可以通过dp[j - weight[j]]推导出来，dp[j - weight[i]]表示容量为j - weight[i]的背包所背的最大价值。

   dp[j - weight[i]] + value[i] 表示 容量为 j - 物品i重量 的背包 加上 物品i的价值。（也就是容量为j的背包，放入物品i了之后的价值即：dp[j]）

   此时dp[j]有两个选择，一个是取自己dp[j]，一个是取dp[j - weight[i]] + value[i]，指定是取最大的，毕竟是求最大价值，

3. 一维dp数组如何初始化

   关于初始化，一定要和dp数组的定义吻合，否则到递推公式的时候就会越来越乱。

   dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。

   那么dp数组除了下标0的位置，初始为0，其他下标应该初始化多少呢？

   dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

   dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了，如果题目给的价值有负数，那么非0下标就要初始化为负无穷。

   这样才能让dp数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了。

4. 一维dp数组的遍历顺序

   for(int i = 0; i < weight.size(); i++){//遍历物品
       //为什么j>=weight[i]是因为你需要让背包剩余的容量大于物品的容量，j - weight[i]要大于零
       //倒序就是保证物品只放一次
   	for(int j = bagWeight; j >= weight[i]; j--){//遍历背包容量
           dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
       }
   }
   

   二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。

   为什么呢？

   举一个例子：物品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

   所以从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。

   那么问题又来了，为什么二维dp数组历的时候不用倒叙呢？

   因为对于二维dp，dp[i] [j]都是通过上一层即dp[i - 1] [j]计算而来，本层的dp[i] [j]并不会被覆盖！

   （如何这里读不懂，大家就要动手试一试了，空想还是不靠谱的，实践出真知！）

   再来看看两个嵌套for循环的顺序，代码中是先遍历物品嵌套遍历背包容量，那可不可以先遍历背包容量嵌套遍历物品呢？

   不可以！

   因为一维dp的写法，背包容量一定是要倒序遍历（原因上面已经讲了），如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品。

   （这里如果读不懂，就在回想一下dp[j]的定义，或者就把两个for循环顺序颠倒一下试试！）

   所以一维dp数组的背包在遍历顺序上和二维其实是有很大差异的！，这一点大家一定要注意。

void test_1_wei_bakg_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++){
        //为什么j>=weight[i]是因为你需要让背包剩余的容量大于物品的容量，j - weight[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();
}

为什么分割等和子集可以理解为动态规划………………………………

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意:

每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:

输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2:

输入: [1, 2, 3, 5]

输出: false

解释: 数组不能分割成两个元素和相等的子集.

【分析】

这道题目初步看，是如下两题几乎是一样的，大家可以用回溯法，解决如下两题

• 698.划分为k个相等的子集
• 473.火柴拼正方形

这道题目是要找是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

那么只要找到集合里能够出现 sum / 2 的子集总和，就算是可以分割成两个相同元素和子集了。

本题是可以用回溯暴力搜索出所有答案的，但最后超时了，也不想再优化了，放弃回溯，直接上01背包吧。

背包问题，大家都知道，有N件物品和一个最多能被重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。【每件物品只能用一次】，求解将哪些物品装入背包里物品价值总和最大。

要注意题目描述中商品是不是可以重复放入。

即一个商品如果可以重复多次放入是完全背包，而只能放入一次是01背包，写法还是不一样的。

要明确本题中我们要使用的是01背包，因为元素我们只能用一次。

只有确定了如下四点，才能把01背包问题套到本题上来。

• 背包的体积为sum / 2
• 背包要放入的商品（集合里的元素）重量为元素的数值，价值也为元素的数值
• 背包如何正好装满，说明找到了总和为 sum / 2 的子集。
• 背包中每一个元素是不可重复放入。

以上分析完，我们就可以套用01背包，来解决这个问题了。

动规五步曲：

1. 确定dp数组以及下标的含义

   01背包中，dp[i]表示：容量为i的背包，所背的物品价值可以最大为dp[i]。

   dp[i]表示背包总容量是i，最大可以凑成i的子集总和为dp[i]

2. 确定递推公式

   01背包中递推公式为：dp[j] = max(dp[j], dp[i - weight[i]] + value[i]);

   套到本题：相当于背包里放入数值，那么物品为i的重量是nums[i],其价值也为nums[i](为什么)

   所以本题的递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

3. dp数组如何初始化

   从dp[j]的定义来看，首先dp[0]一定是0。

   如果如果题目给的价值都是正整数那么非0下标都初始化为0就可以了，如果题目给的价值有负数，那么非0下标就要初始化为负无穷。

   这样才能让dp数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了。

   本题题目中 只包含正整数的非空数组，所以非0下标的元素初始化为0就可以了。

   // 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200
   // 那么背包内总和不会大于20000，所以定义一个20000大的数组。
   vector<int> dp(20001, 0);
   

4. 确定遍历顺序

   如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环 倒序遍历。

   // 开始 01背包 
   for(int i = 0; i < nums.size(); i++) {
       for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入，所以从大到小遍历
           //dp[j]:j凑成最大子集的和为dp[j]
           dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
       }
   }
   

5. 举例推导dp数组

   dp[i]的数值一定是小于等于i的。

   如果dp[i] == i 说明，集合中的子集总和正好可以凑成总和i，理解这一点很重要。

   用例1，输入[1,5,11,5] 为例，如图：

   

综上所述C++代码：

//使用滚动数组的方法也是最简单最理解的方法
//时间复杂度：O(n)
//空间复杂度：O(n)
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;

        // dp[i]中的i表示背包内总和
        // 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200
        // 那么背包内总和不会大于20000，所以定义一个20000大的数组。
        //当背包的容量很大时候建议考虑滚动数组求解，滚动数组相对于二维数组来说，就是如果是01背包则对容量遍历时应该采用的倒序遍历
        vector<int> dp(20001, 0); 
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
        }
        if (sum % 2 == 1) 
            return false;
        int target = sum / 2;

        // 开始 01背包 
        for(int i = 0; i < nums.size(); i++) {//没有等号
            //对于滚动数组来说，用一维数组来代替本该的二维数组，因为是01背包，每一个元素不可以重复放入，所以应该是从大到小遍历的
            for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入，所以从大到小遍历
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        // 集合中的元素正好可以凑成总和target 
        if (dp[target] == target) return true;
        return false;      
    }
};

//方法二：使用二维dp数组，套用01背包解决：解决问题的关键就是找到物品和背包容量
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int len = nums.size();
        int sum = 0;
        for(int i = 0; i < len; i++)
        {
            sum += nums[i];
        }
        if(sum % 2)
            return false;
        int bagWeight = sum / 2;
        vector<vector<int>> dp(len, vector<int>(bagWeight + 1, 0));
        //动条数组的初始化
        for(int i = nums[0]; i <= bagWeight; i++)
        {
            dp[0][i] = nums[0];
        }
        for(int i = 1; i < len; i++)
        {
            for(int j = 0; j <= bagWeight; j++)
            {
                if(nums[i] > j)
                    dp[i][j] = dp[i-1][j];
                else
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]] + nums[i]);
            }
        }
        return dp[len - 1][bagWeight] == bagWeight;
    }
};

01背包相对于本题，主要要理解，题目中物品是nums[i]，重量是nums[i]i，价值也是nums[i]，背包体积是sum/2。

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。

示例：

输入：[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]，这就是最优值。

提示：

1 <= stones.length <= 30
1 <= stones[i] <= 1000

[分析]

本题其实就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。

本题物品的重量为store[i]，物品的价值也为store[i]。

对应着01背包里的物品重量weight[i]和 物品价值value[i]。

动态规划五步曲：

1. 确定dp数组以及下标的含义

   dp[j]表示：容量（其实就是重量）为j的背包，最多可以背dp[j]这么重的石头

2. 确定递推公式：

   dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);

3. dp数组的初始化

   既然dp[j] 中的j表示容量，那么最大容量是多少呢，就是所有石头的重量和。

   因为提示中给出1<=stones.length <=30, 1<=sones[i]<=1000,所以最大重量就是30*1000.

   而我们要求的target其实只是最大重量的一半，所以dp数组开到15000大小就可以了。

   当然也可以把石头遍历一遍，计算出石头总重量 然后除2，得到dp数组的大小。

   我这里就直接用15000了。

   接下来就是如何初始化dp[j]呢，因为重量都不会是负数，所以dp[j]都初始化为0就可以了，这样在递归公式dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])中dp[j]才不会初始值所覆盖。

   vector<int> dp(15001, 0);
   

4. 确定遍历顺序

   如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒叙遍历！

【c++代码如下】

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]);
    }
}

5. 举例推导dp数组

   举例，输入：[2,4,1,1]，此时target = (2 + 4 + 1 + 1)/2 = 4 ，dp数组状态图如下：

   

最后dp[target]里是容量为target的背包所能背的最大重量。

那么分成两堆石头，一堆石头的总重量是dp[target]，另一堆就是sum - dp[target]。

在计算target的时候，target = sum / 2 因为是向下取整，所以sum - dp[target] 一定是大于等于dp[target]的。

那么相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target]。

【c++代码】

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;
        for(int i = 0; i < stones.size(); i++){
            sum += stones[i];
        }
        int target = sum / 2;//当sum为奇数的时候向下兼容就是说sum/2 >= target
        vector<int> dp(target+1, 0);
        for(int i = 0; i < stones.size(); i++){//遍历物品
            for(int j = target; j >= stones[i]; j--){//遍历背包
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return (sum - dp[target]) - dp[target];
    }
};

给定一个非负正整数数组，a1，a2，a3…a4，和一个目标数S。现在你有两个符号+和-。对于数组中的任意一个整数，你都可以+或-中选择一个符号添加在前面。
返回可以使最终数组和为目标数S的所有添加符号的方法数。

输入：nums: [1, 1, 1, 1, 1], S: 3
输出：5
解释：

-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

一共有5种方法让最终目标和为3。

提示：

数组非空，且长度不会超过 20 。
初始的数组的和不会超过 1000 。
保证返回的最终结果能被 32 位整数存下。

【思路】

这道题目咋眼一看和动态规划背包啥的也没啥关系。

本题要如何使表达式结果为target，

既然为target，那么就一定有 left组合 - right组合 = target。

left + right等于sum，而sum是固定的。

公式来了， left - (sum - left) = target -> left = (target + sum)/2 。

target是固定的，sum是固定的，left就可以求出来。

此时问题就是在集合nums中找出和为left的组合。

【回溯算法】

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
        if (sum == target) {
            result.push_back(path);
        }
        // 如果 sum + candidates[i] > target 就终止遍历
        for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates, target, sum, i + 1);
            sum -= candidates[i];
            path.pop_back();

        }
    }
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) sum += nums[i];
        if (S > sum) return 0; // 此时没有方案
        if ((S + sum) % 2) return 0; // 此时没有方案，两个int相加的时候要各位小心数值溢出的问题
        int bagSize = (S + sum) / 2; // 转变为组合总和问题，bagsize就是要求的和

        // 以下为回溯法代码
        result.clear();
        path.clear();
        sort(nums.begin(), nums.end()); // 需要排序
        backtracking(nums, bagSize, 0, 0);
        return result.size();
    }
};

【动态规划】

如何转化为01背包问题呢。

假设加法的总和为x，那么减法对应的总和就是sum - x。

所以我们要求的是 x - (sum - x) = S

x = (S + sum) / 2

此时问题就转化为，装满容量为x背包，有几种方法。

大家看到(S + sum) / 2 应该担心计算的过程中向下取整有没有影响。

这么担心就对了，例如sum 是5，S是2的话其实就是无解的，所以：

因为每个物品（题目中的1）只用一次！

这次和之前遇到的背包问题不一样了，之前都是求容量为j的背包，最多能装多少。

1. 确定dp数组以及下标的含义

   dp[j]:填满（包括j)这么大容积的包，有dp[i]种方法

   其实也可以使用二维dp数组来求解本题，dp[i] [j]：使用 下标为[0, i]的nums[i]能够凑满j（包括j）这么大容量的包，有dp[i] [j]种方法。

2. 确定递推公式

   有哪些来源可以推出dp[j]

   不考虑nums[i]的情况下，填满容量为j - nums[i]的背包，有dp[j - nums[i]]中方法。

   那么只要搞到**nums[i]**的话，凑成dp[j]就有dp[j - nums[i]] 种方法。

   举一个例子,nums[i] = 2：dp[3]，填满背包容量为3的话，有dp[3]种方法。

   那么只需要搞到一个2（nums[i]），有dp[3]方法可以凑齐容量为3的背包，相应的就有多少种方法可以凑齐容量为5的背包。

   那么需要把 这些方法累加起来就可以了，dp[i] += dp[j - nums[j]]

   所以求组合类问题的公式，都是类似这种：???

   //dp[j] += dp[j - nums[i]];
   dp[j] = dp[j] + dp[j - nums[i]];
   

   这个公式在后面在讲解背包解决排列组合问题的时候还会用到！

3. dp数组如何初始化

   输入：nums:[1,1,1,1,1],S:3

   bagSize = (S + sum)/2 = (3+5)/2 = 4;

//时间复杂度：O(n*m)n为正整数，m为背包容量
//空间复杂度：O(m)m为背包容量
class Solution{
public:
    int findTargetSumWays(vector<int>& nums, int S){
        int sum = 0;
        for(int i = 0; i < nums.size(); i++)
            sum += nums[i];
        if(S > sum) return 0;//此时没有方案
        if((S + sum) % 2 == 1 )return 0;
        int bagSize = (S + sum) / 2;
        vector<int> dp(bagSize + 1, 0);
        dp[0] = 1;
        for(int i = 0; i < nums.size(); i++){
            for(int j = bagSize; j >= nums[i]; j--){
                /*
               	遍历nums数组，对于每个元素（选或者不选）
               		若当前遍历的元素nums[i]不选，则此时满足背包容量j的方法数不变，不进行任何操作；
               		若当前便利的元素nums[i]不选择，则此时背包容量减少了nums[i](j-nums[i]),此时满足背包容量j的方法数，应该在dp[j]的基础上加上闭包容量j-nums[i]时的方法数，
               	为什么下面的时加法：是因为本题要求得到的时方法数，并不是最大的方法数，所以需要求和。
                */
                dp[j] = dp[j] + dp[j - nums[i]];
            }
        }
        return dp[bagSize];
    }
}

给你一个二进制字符串数组 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 。

示例 2：
输入：strs = [“10”, “0”, “1”], m = 1, n = 1
输出：2
解释：最大的子集是 {“0”, “1”} ，所以答案是 2 。

提示：

1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] 仅由 ‘0’ 和 ‘1’ 组成
1 <= m, n <= 100

【三维】

【三维】

和01背包很像：1个变量需要2维，2个变量则需要3维

定义三维数组dp，**其中dp[i] [j] [k]表示前i个字符串中，使用j个0和k个1的情况下最多可以得到的字符串数量。**假设数组str长度维l，则最终答案维dp[l] [m] [n]。

当没有任何字符串可以使用时，可以得到的字符串数量只能是0，因此动态规划的边界条件是:当i = 0时，对任意0 <= i <=j时，对于strs中的第i个字符串(计数从1开始),首先遍历该字符串得到其中的0和1的数量，分别记为zeros和ones，然后对于0 <= j <= m和0 <= k <= n，计算dp[i] [j] [k]的值。

当0和1的容量分别时j和k时，考虑以下两种情况：

• 如果j < zeros或者k <ones,则不能选第i个字符串，此时有dp[i] [j] [k] = dp[i-1] [j] [k];
• 如果j >= zeros 且 k >= ones,则如果不选第i个字符串，有dp[i] [j] [k] = dp[i-1] [j] [k],如果选第i个字符串，有dp[i] [j] [k] = dp[i-1] [j-zeros] [k-ones] + 1,dp[i] [j] [k] 的值应取上面两项中最大值。

时间复杂度为：O(lmn)

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) 
    {
        int Len = strs.size();
        int dp[Len+1][m+1][n+1];  //为什么定义数组时要用+1的操作  
        memset(dp, 0, sizeof(dp));

        for (int k = 1; k < Len + 1; k ++)
        {
            int cnt0 = 0,    cnt1 = 0;
            for (char & c : strs[k-1])
                cnt0 += (c=='0'), cnt1 += (c=='1');

            for (int i = 0; i < m + 1; i ++)
            {
                for (int j = 0; j < n + 1; j ++)
                {
                    //不选择第k件物品
                    int a = dp[k-1][i][j];
                    //选择第k件物品(前提是有足够的m与n的额度)
                    int b = (i >= zeroNum && j >= oneNum)?dp[k-1][i-zeroNum][j-oneNum]+1:0;
                    dp[k][i][j] = max(a, b);
          /*          
                    dp[k][i][j] = dp[k-1][i][j];
                    if ((i - cnt0 >= 0) && (j - cnt1 >= 0))
                        dp[k][i][j] = max(dp[k][i][j], dp[k-1][i-cnt0][j-cnt1] + 1);*/
                }
            }
        }

        return  dp[Len][m][n];
    }
};

二维dp

可以把外循环去掉，但是要注意循环的顺序和01背包一样，逆序以确保优化时取得值为旧值

【思路】

注意完全背包与01背包的区别

多重背包是每个物品，数量不同的情况。

本题中strs 数组里的元素就是物品，每个物品都是一个！

而m 和 n相当于是一个背包，两个维度的背包。

理解成多重背包的同学主要是把m和n混淆为物品了，感觉这是不同数量的物品，所以以为是多重背包。

只不过这个背包由两个维度，一个是m一个是n，而不同长度的字符串就是不同大小的待装物品，且只能装一次。

动态规划五步曲：

1. 确定dp数组以及下标的含义

   dp[i] [j]: 最多由 i 个0和 j 个1的strs的最大子集的大小为dp[i] [j]，就是横坐标为0的个数，纵坐标为1的个数

2. 确定递推公式

   dp[i] [j]:可以由前一个strs里的字符串导出来，strs里的字符串由zeorNum个0，oneNum个1。

   dp[i] [j] 就可以是 dp[i - zeroNum] [j - oneNum] + 1。

   然后我们在遍历的过程中，取dp[i] [j]的最大值。

   [难懂]所以递推公式：dp[i] [j] = max(dp[i] [j], dp[i - zeroNum] [j - oneNum] + 1);

   此时大家可以回想一下01背包的递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

   对比一下就会发现，字符串的zeroNum和oneNum相当于物品的重量（weight[i]），字符串本身的个数相当于物品的价值（value[i]）。

   这就是一个典型的01背包！ 只不过物品的重量有了两个维度而已。

3. dp数组的初始化

   01背包的dp数组初始化为0就可以。

   因为物品价值不会是负数，初始为0，保证递推的时候dp[i] [j]不会被初始值覆盖。

4. 确定遍历顺序

   01背包一定是外层for循环遍历物品，内层for循环遍历背包容量且从后向前遍历！

   物品就是strs里的字符串，背包容量就是题目描述中的m和n。

   for(string str : strs){//遍历物品
   	int oneNum = 0, zeroNum = 0;
       for(char  c : str){
   		if(c == '0')
               zeroNum++;
           else
               oneNum++;
       }
       
       for(int i = m; i >= zeroNum; i--){//遍历背包容量且从后向前遍历
           for(int j = n; j >= oneNum; j--){
               //zeronum是当c等于str中的一个时0个数，onenum时此时1的个数，加1是加它自身的个数
               dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
           }
       }
   }
   

5. 举例推导dp数组

   以输入：[“10”,“0001”,“111001”,“1”,“0”]，m = 3，n = 3为例

   最后dp数组的状态如下所示：

   

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp =  vector<vector<int>>(m + 1, vector<int>(n + 1, 0));
       
        for(string str : strs){//遍历物品
         	int zeroNum = 0, oneNum = 0;//必须每次遍历都要重置zeroNum于oneNum
            for(char c : str){
                if(c == '0')
                    zeroNum++;
                else
                    oneNum++;
            }
            //因为是二维数组所以需要两个for循环遍历
            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];
    }
};

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

[重点]就是完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。

在下面的讲解中，我依然举这个例子：