image.png

动态规划的解题步骤

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

    开刷

    509. 斐波那契数

    题目

    image.png

    思路

    dp[i]的定义为：第i个数的斐波那契数值是dp[i]
    状态转移方程 dp[i] = dp[i - 1] + dp[i - 2]
    1. dp[0] = 0;
    2. dp[1] = 1;

    代码

    1. func fib(n int) int {
    2.  if n < 2{
    3.      return n
    4.  }
    5.  dp := make([]int,n+1)
    6.  dp[0] = 0
    7.  dp[1] = 1
    8.  for i := 2;i<=n;i++{
    9.      dp[i] = dp[i-1]+dp[i-2]
    10.  }
    11.  return dp[n]
    12. }

    70. 爬楼梯

    题目

    image.png

    思路

    dp[i]： 爬到第i层楼梯，有dp[i]种方法
    dp[1] = 1，dp[2] = 2
    dp[i] = dp[i - 1] + dp[i - 2]

    代码

    1. func climbStairs(n int) int {
    2.  if n < 3{
    3.      return n
    4.  }
    5.  var dp []int
    6.  dp = make([]int,n+1)
    7.  dp[1] = 1
    8.  dp[2] = 2
    9.  for i := 3;i<=n;i++{
    10.      dp[i] = dp[i-1] + dp[i-2]
    11.  }
    12.  return dp[n]
    13. }

    746. 使用最小花费爬楼梯

    题目

    image.png
    image.png

    思路

    dp[i]的定义：到达第i个台阶所花费的最少体力为dp[i]。
    dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]，注意这里为什么是加cost[i]，而不是cost[i-1],cost[i-2]之类的，因为题目中说了：每当你爬上一个阶梯你都要花费对应的体力值。
    dp[0] = cost[0]; dp[1] = cost[1];

代码

  1. func minCostClimbingStairs(cost []int) int {
  3.     dp := make([]int,len(cost))
  4.     dp[0] = cost[0]
  5.     dp[1] = cost[1]
  6.     for i := 2;i<len(cost);i++{
  7.         dp[i] = min(dp[i-1],dp[i-2])+cost[i]
  8.     }
  9.     return min(dp[len(cost)-1],dp[len(cost)-2])
  10. }
  11. func min(a,b int)int{
  12.     if a<b{
  13.         return a
  14.     }else{
  15.         return b
  16.     }
  17. }

62. 不同路径

题目

image.png
image.png

思路

dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因为dp[i][j]只有这两个方向过来。
dp[i][0]一定都是1，因为从(0, 0)的位置到(i, 0)的路径只有一条，那么dp[0][j]也同理。

代码

  1. func uniquePaths(m int, n int) int {
  2.     dp := make([][]int,m)
  3.     for i:=0;i<m;i++{
  4.         dp[i] = make([]int,n)
  5.     }
  6.     for i := 0;i<n;i++{
  7.         dp[0][i] = 1
  8.     }
  9.     for i := 0;i<m;i++{
  10.         dp[i][0] = 1
  11.     }
  12.     for i := 1;i<m;i++{
  13.         for j:=1;j<n;j++{
  14.             dp[i][j] = dp[i-1][j] + dp[i][j-1]
  15.         }
  16.     }
  17.     return dp[m-1][n-1]
  18. }

63. 不同路径 II

题目

image.png
image.png
image.png

思路

dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。
因为有了障碍，(i, j)如果就是障碍的话应该就保持初始状态（初始状态为0）。
给第一行或者第一列赋值的时候，如果遇到障碍物，那后面都不可以赋值为1了。
如果障碍物在中间出现了，那该点就到达不了就是0。
其他的都和上面一题一样。

代码

  1. func uniquePathsWithObstacles(obstacleGrid [][]int) int {
  2.     m, n := len(obstacleGrid), len(obstacleGrid[0])
  3.     // 定义一个dp数组
  4.     dp := make([][]int, m)
  5.     for i, _ := range dp {
  6.         dp[i] = make([]int, n)
  7.     }
  8.     // 初始化, 如果是障碍物, 后面的就都是0, 不用循环了
  9.     for i := 0; i < m && obstacleGrid[i][0] == 0; i++ {
  10.         dp[i][0] = 1
  11.     }
  12.     for i := 0; i < n && obstacleGrid[0][i] == 0; i++ {
  13.         dp[0][i] = 1
  14.     }
  15.     // dp数组推导过程
  16.     for i := 1; i < m; i++ {
  17.         for j := 1; j < n; j++ {
  18.             // 如果obstacleGrid[i][j]这个点是障碍物, 那么dp[i][j]保持为0
  19.             if obstacleGrid[i][j] != 1 {
  20.                 // 否则我们需要计算当前点可以到达的路径数
  21.                 dp[i][j] = dp[i-1][j] + dp[i][j-1]
  22.             }
  23.         }
  24.     }
  25.     return dp[m-1][n-1]
  26. }

343. 整数拆分

题目

image.png

思路

dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。
其实可以从1遍历j，然后有两种渠道得到dp[i].
一个是j (i - j) 直接相乘。
一个是j dp[i - j]，相当于是拆分(i - j)

代码

  1. func integerBreak(n int) int {
  2.     /**
  3.     动态五部曲
  4.     1.确定dp下标及其含义
  5.     2.确定递推公式
  6.     3.确定dp初始化
  7.     4.确定遍历顺序
  8.     5.打印dp
  9.     **/
  10.     dp:=make([]int,n+1)
  11.     dp[1]=1
  12.     dp[2]=1
  13.     for i:=3;i<n+1;i++{
  14.         for j:=1;j<i-1;j++{
  15. // i可以差分为i-j和j。由于需要最大值，故需要通过j遍历所有存在的值，取其中最大的值作为当前i的最大值，在求最大值的时候，一个是j与i-j相乘，一个是j与dp[i-j].
  16.             dp[i]=max(dp[i],max(j*(i-j),j*dp[i-j]))
  17.         }
  18.     }
  19.     return dp[n]
  20. }
  21. func max(a,b int) int{
  22.     if a>b{
  23.         return a
  24.     }
  25.     return b
  26. }

96. 不同的二叉搜索树

题目

image.png
image.png

思路

这个题后面再回来看！！！！！

代码

01背包

image.png

二维dp数组01背包理论讲解

image.png

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

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

  1. 确定递推公式

两个方向推出来dp[ i ][ j ]：

  • 不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以被背包内的价值依然和前面相同。)
  • 放物品i：由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]);

  1. dp数组如何初始化

首先从dp[i][j]的定义出发，如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。
image.png
状态转移方程 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的物品的时候，各个容量的背包所能存放的最大价值。
那么很明显当 j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。
当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。
image.png

  1. 确定遍历顺序

有两个遍历的维度：物品与背包重量。
要理解递归的本质和递推的方向。
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 递归公式中可以看出dp[i][j]是靠dp[i-1][j]和dp[i - 1][j - weight[i]]推导出来的。
dp[i-1][j]和dp[i - 1][j - weight[i]] 都在dp[i][j]的左上角方向（包括正上方向），
那么先遍历物品，再遍历背包的过程如图所示：
image.png
再来看看先遍历背包，再遍历物品呢，如图：
image.png
大家可以看出，虽然两个for循环遍历的次序不同，但是dp[i][j]所需要的数据就是左上角，根本不影响dp[i][j]公式的推导！
但先遍历物品再遍历背包这个顺序更好理解。
背包问题里，两个for循环先后循序是非常有讲究的，理解遍历顺序其实比理解推导公式难多了。

代码

  1. func test_2_wei_bag_problem1(weight, value []int, bagweight int) int {
  2.     // 定义dp数组
  3.     dp := make([][]int, len(weight))
  4.     for i, _ := range dp {
  5.         dp[i] = make([]int, bagweight+1)
  6.     }
  7.     // 初始化
  8.     for j := bagweight; j >= weight[0]; j-- {
  9.         dp[0][j] = dp[0][j-weight[0]] + value[0]
  10.     }
  11.     // 递推公式
  12.     for i := 1; i < len(weight); i++ {
  13.         //正序,也可以倒序
  14.         for  j := weight[i];j<= bagweight ; j++ {
  15.             dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])
  16.         }        
  17.     }
  18.     return dp[len(weight)-1][bagweight]
  19. }
  21. func max(a,b int) int {
  22.     if a > b {
  23.         return a
  24.     }
  25.     return b
  26. }
  28. func main() {
  29.     weight := []int{1,3,4}
  30.     value := []int{15,20,30}
  31.     test_2_wei_bag_problem1(weight,value,4)
  32. }

一维dp数组01背包理论讲解

提前总结（详细的在下面）
1、为什么背包是倒序：
因为，如果是正序的话，在i 等于0的情况下，遍历背包，
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
2、为什么外层必须是物品、内层是背包
第一次遍历的时候，j = 5，i从0到n，意思就是背包容量为5的时候在初始化时，dp数组都为0，
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
i 为0，dp[5] 放的是物品0
i为1，dp[5] 放的是物品0
后面都是这样，所以这样背包就只能放进去一个物品。

在使用二维数组的时候，递推公式：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的背包，价值总和最大是多少。

  1. 确定dp数组的定义

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

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

dp[j]为 容量为j的背包所背的最大价值，那么如何推导dp[j]呢？
dp[j]可以通过dp[j - weight[i]]推导出来，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数组中的dp[i-1][j]，即不放物品i，一个是取dp[j - weight[i]] + value[i]，即放物品i，指定是取最大的，毕竟是求最大价值，（这里注意，不放物品时候，背包容量还是j不变，所以可以直接等于dp[j]。如果放了就dp[j - weight[i]] + value[i]，背包容量也有所变化。）
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

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

dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。
dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。
这样才能让dp数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了。
那么我假设物品价值都是大于0的，所以dp数组初始化的时候，都初始为0就可以了。

  1. 一维dp数组遍历顺序

    1. for(int i = 0; i < weight.size(); i++) { // 遍历物品
    2.  for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
    3.      dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    5.  }
    6. }

    这里大家发现和二维dp的写法中，遍历背包的顺序是不一样的！
    二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。
    为什么呢？
    倒序遍历是为了保证物品i只被放入一次！。但如果一旦正序遍历了，那么物品0就会被重复加入多次！
    举一个例子：物品0的重量weight[0] = 1，价值value[0] = 15
    如果正序遍历（这里举例是i == 0情况下的说明，一定注意）
    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]就只会放入一个物品，即：背包里只放入了一个物品。这里解释：第一次遍历的时候，j = 5，i从0到n，那么dp[j] 只能放进去一个物品。因为容量很大，且初始化都是0，所以遇到哪一个物品都可以放进去，就只能放进去一个。
    倒序遍历的原因是，本质上还是一个对二维数组的遍历，并且右下角的值依赖上一层左上角的值，因此需要保证左边的值仍然是上一层的，从右向左覆盖。

  2. 举例推导dp数组

一维dp，分别用物品0，物品1，物品2 来遍历背包，最终得到结果如下：
image.png
上面这个图很重要，能帮助我们理解。一定要记住外面是i的大循环，所以背包一定要倒序。从右往左填的。
记住递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
第一次，i = 0后面都是15这个不用多说。因为只有一个物品。
第二次i = 1，上面图说的是用物品1遍历背包，从递推公式理解，因为上面所有的dp[j]都已经初始化为15过了，看看这个物品要不要放进去，不放就是等于dp[j]还是原来的15，放的话，就是dp[5 - weight[1]]+value[1] = dp[2] + 20。这里dp[ 2 ]等于15。所以等于15+20=35。
总结下来就是，dp[j]从两个方向推导过来的，放第i个和不放第i个。关键的是要倒序保证每个物品只能放进去一次。这里其实主要是针对i=0来说的。因为他的初始化都是0。后面i不断变化的时候，为什么遍历背包的时候要大于等于weights[i]呢，其实是如果小于weights[i]的话，就没必要讨论了，第i个物品肯定放不进去。前面讨论的都是背包容量肯定是大于当前的物品容量的。
这里我有一点疑问就是，如果后面物品性价比大于之前的呢，那之前的物品怎么从背包里拿出来，然后把性价比高的放进去呢？
就比如现在遍历到了i = 1，dp[3] = dp[3 - weight[1]]+value[1] = 20,这就把之前的0号物品拿出去了，把当前的放进去了

代码

  1. func test_1_wei_bag_problem(weight, value []int, bagWeight int) int {
  2.     // 定义 and 初始化
  3.     dp := make([]int,bagWeight+1)
  4.     // 递推顺序
  5.     for i := 0 ;i < len(weight) ; i++ {
  6.         // 这里必须倒序,区别二维,因为二维dp保存了i的状态
  7.         for j:= bagWeight; j >= weight[i] ; j-- {
  8.             // 递推公式
  9.             dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
  10.         }
  11.     }
  12.     //fmt.Println(dp)
  13.     return dp[bagWeight]
  14. }
  16. func max(a,b int) int {
  17.     if a > b {
  18.         return a
  19.     }
  20.     return b
  21. }
  24. func main() {
  25.     weight := []int{1,3,4}
  26.     value := []int{15,20,30}
  27.     test_1_wei_bag_problem(weight,value,4)
  28. }

416. 分割等和子集

题目

image.png

思路

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

  • 背包的体积为sum / 2
  • 背包要放入的商品（集合里的元素）重量为元素的数值，价值也为元素的数值
  • 背包如果正好装满，说明找到了总和为 sum / 2 的子集。
  • 背包中每一个元素是不可重复放入。
  1. 确定dp数组以及下标的含义

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

  1. 确定递推公式

01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
本题，相当于背包里放入数值，那么物品i的重量是nums[i]，其价值也是nums[i]。
所以递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])

  1. dp数组如何初始化

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

  1. 确定遍历顺序

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

  1. // 开始 01背包
  2. for(int i = 0; i < nums.size(); i++) {
  3.     for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入，所以从大到小遍历
  4.         dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
  5.     }
  6. }
  1. 举例

dp[j]的数值一定是小于等于j的。
如果dp[j] == j 说明，集合中的子集总和正好可以凑成总和j，理解这一点很重要。
用例1，输入[1,5,11,5] 为例，如图：
image.png
最后dp[11] == 11，说明可以将这个数组分割成两个子集，使得两个子集的元素和相等。

代码

  1. func canPartition(nums []int) bool {
  2.     if sum(nums) % 2 != 0{
  3.         return false
  4.     }
  5.     Sum := sum(nums) / 2
  6.     dp := make([]int,Sum+1)
  7.     for i := 0;i < len(nums);i++{
  8.         for j := Sum;j>=nums[i];j--{
  9.             dp[j] = max(dp[j],dp[j-nums[i]]+nums[i])
  10.         }
  11.     }
  12.     return dp[Sum] == Sum
  13. }
  14. func sum(nums []int)int{
  15.     res := 0
  16.     for _,v := range nums{
  17.         res += v
  18.     }
  19.     return res
  20. }
  21. func max(a,b int) int {
  22.     if a > b {
  23.         return a
  24.     }
  25.     return b
  26. }

1049. 最后一块石头的重量 II

题目

image.png

思路

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

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

  1. 确定递推公式

01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
本题则是：dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
一些同学可能看到这dp[j - stones[i]] + stones[i]中 又有- stones[i] 又有+stones[i]，看着有点晕乎。
还是要牢记dp[j]的含义，要知道dp[j - stones[i]]为 容量为j - stones[i]的背包最大所背重量。

  1. dp数组如何初始化

既然 dp[j]中的j表示容量，那么最大容量（重量）是多少呢，就是所有石头的重量和。
因为提示中给出1 <= stones.length <= 30，1 <= stones[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]才不会初始值所覆盖。

  1. 确定遍历顺序

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

  1. 举例推导dp数组

举例，输入：[2,4,1,1]，此时target = (2 + 4 + 1 + 1)/2 = 4 ，dp数组状态图如下：
image.png
最后dp[target]里是容量为target的背包所能背的最大重量。
那么分成两堆石头，一堆石头的总重量是dp[target]，另一堆就是sum - dp[target]。
在计算target的时候，target = sum / 2 因为是向下取整，所以sum - dp[target] 一定是大于等于dp[target]的。

代码

  1. func lastStoneWeightII(stones []int) int {
  2.     // 15001 = 30 * 1000 /2 +1
  3.     dp := make([]int, 15001)
  4.     // 求target
  5.     sum := 0
  6.     for _, v := range stones {
  7.         sum += v
  8.     }
  9.     target := sum / 2
  10.     // 遍历顺序
  11.     for i := 0; i < len(stones); i++ {
  12.         for j := target; j >= stones[i]; j-- {
  13.             // 推导公式
  14.             dp[j] = max(dp[j], dp[j-stones[i]]+stones[i])
  15.         }
  16.     }
  17.     return sum - 2 * dp[target]
  18. }
  20. func max(a, b int) int {
  21.     if a > b {
  22.         return a
  23.     }
  24.     return b
  25. }

494. 目标和

题目

image.png

思路

如何转化为01背包问题呢。
假设加法的总和为x，那么减法对应的总和就是sum - x。
所以我们要求的是 x - (sum - x) = S
x = (S + sum) / 2
此时问题就转化为，装满容量为x背包，有几种方法。
大家看到(S + sum) / 2 应该担心计算的过程中向下取整有没有影响。
这么担心就对了，例如sum 是5，S是2的话其实就是无解的。
同时如果 S的绝对值已经大于sum，那么也是没有方案的。
再回归到01背包问题，为什么是01背包呢？
因为每个物品（题目中的1）只用一次！
这次和之前遇到的背包问题不一样了，之前都是求容量为j的背包，最多能装多少。
本题则是装满有几种方法。其实这就是一个组合问题了。

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

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

  1. 确定递推公式

有哪些来源可以推出dp[j]呢？
不考虑nums[i]的情况下，填满容量为j - nums[i]的背包，有dp[j - nums[i]]种方法。
那么只要搞到nums[i]的话，凑成dp[j]就有dp[j - nums[i]] 种方法。
例如：dp[j]，j 为5，dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法

  • 已经填进去1（nums[i]） 的话，有 dp[4]种方法 凑成 dp[5]。
  • 已经填进去2（nums[i]） 的话，有 dp[3]种方法 凑成 dp[5]。
  • 已经填进去3（nums[i]） 的话，有 dp[2]中方法 凑成 dp[5]
  • 已经填进去4（nums[i]） 的话，有 dp[1]中方法 凑成 dp[5]
  • 已经填进去5 （nums[i]）的话，有 dp[0]中方法 凑成 dp[5]

那么凑整dp[5]有多少方法呢，也就是把 所有的 dp[j - nums[i]] 累加起来。
所以求组合类问题的公式，都是类似这种：
dp[j] += dp[j - nums[i]]
其实可以这样理解，如果不选第i个元素，还是dp[j]如果选了就是dp[j - nums[i]]，因为是求组合的，所以肯定两种情况都要算上。因为是求的多少种方法，并不需要加上价值。

  1. dp数组如何初始化

从递归公式可以看出，在初始化的时候dp[0] 一定要初始化为1，因为dp[0]是在公式中一切递推结果的起源，如果dp[0]是0的话，递归结果将都是0。
dp[0] = 1，理论上也很好解释，装满容量为0的背包，有1种方法，就是装0件物品。
dp[j]其他下标对应的数值应该初始化为0，从递归公式也可以看出，dp[j]要保证是0的初始值，才能正确的由dp[j - nums[i]]推导出来。

  1. 确定遍历顺序

nums放在外循环，target在内循环，且内循环倒序。

  1. 举例推导dp数组

输入：nums: [1, 1, 1, 1, 1], S: 3
bagSize = (S + sum) / 2 = (3 + 5) / 2 = 4
dp数组状态变化如下：
image.png
dp[j] += dp[j - nums[i]]

  1.     for i := 0; i < len(nums); i++ {
  2.         for j := bag; j >= nums[i]; j-- {
  3.             //推导公式
  4.             dp[j] += dp[j-nums[i]]
  5.             //fmt.Println(dp)
  6.         }

i = 0时：dp[5] = dp[5] + dp[5 - num[ 0 ]]，因为初始化dp[0] = 1,其他的都是0。所以dp[5]=dp[4] = 0
同理其他的也都是0一直到dp[1] 因为dp之和前一个值有关系。
后面都是这样推导的。
同理其他的也都是0一直到dp[1] 因为dp之和前一个值有关系。

代码

  1. func findTargetSumWays(nums []int, target int) int {
  2.     sum := 0
  3.     for _, v := range nums {
  4.         sum += v
  5.     }
  6.     if abs(target) > sum {
  7.         return 0
  8.     }
  9.     if (sum+target)%2 == 1 {
  10.         return 0
  11.     }
  12.     // 计算背包大小
  13.     bag := (sum + target) / 2
  14.     // 定义dp数组
  15.     dp := make([]int, bag+1)
  16.     // 初始化
  17.     dp[0] = 1
  18.     // 遍历顺序
  19.     for i := 0; i < len(nums); i++ {
  20.         for j := bag; j >= nums[i]; j-- {
  21.             //推导公式
  22.             dp[j] += dp[j-nums[i]]
  23.             //fmt.Println(dp)
  24.         }
  25.     }
  26.     return dp[bag]
  27. }

474. 一和零

题目

image.png

思路

代码

完全背包

理论讲解

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。
image.png
01背包和完全背包唯一不同就是体现在遍历顺序上
首先在回顾一下01背包的核心代码

  1. for(int i = 0; i < weight.size(); i++) { // 遍历物品
  2.     for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
  3.         dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
  4.     }
  5. }

我们知道01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。
而完全背包的物品是可以添加多次的，所以要从小到大去遍历，即：

  1. // 先遍历物品，再遍历背包
  2. for(int i = 0; i < weight.size(); i++) { // 遍历物品
  3.     for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量
  4.         dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
  5.     }
  6. }

dp状态图如下：
image.png
其实还有一个很重要的问题，为什么遍历物品在外层循环，遍历背包容量在内层循环？
这个问题很多题解关于这里都是轻描淡写就略过了，大家都默认遍历物品在外层，遍历背包容量在内层，好像本应该如此一样，那么为什么呢？
难道就不能遍历背包容量在外层，遍历物品在内层？
01背包中二维dp数组的两个for遍历的先后循序是可以颠倒了，一维dp数组的两个for循环先后循序一定是先遍历物品，再遍历背包容量。
在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序同样无所谓！
因为dp[j] 是根据下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以了。
遍历物品在外层循环，遍历背包容量在内层循环，状态如图：
image.png
遍历背包容量在外层循环，遍历物品在内层循环，状态如图：
image.png
看了这两个图，大家就会理解，完全背包中，两个for循环的先后循序，都不影响计算dp[j]。
细心的同学可能发现，全文我说的都是对于纯完全背包问题，其for循环的先后循环是可以颠倒的！
但如果题目稍稍有点变化，就会体现在遍历顺序上。
如果问装满背包有几种方式的话？ 那么两个for循环的先后顺序就有很大区别了
最后，又可以出一道面试题了，就是纯完全背包，要求先用二维dp数组实现，然后再用一维dp数组实现，最后在问，两个for循环的先后是否可以颠倒？为什么？ 这个简单的完全背包问题，估计就可以难住不少候选人了。

代码

  1. // test_CompletePack1 先遍历物品, 在遍历背包
  2. func test_CompletePack1(weight, value []int, bagWeight int) int {
  3.     // 定义dp数组 和初始化
  4.     dp := make([]int, bagWeight+1)
  5.     // 遍历顺序
  6.     for i := 0; i < len(weight); i++ {
  7.         // 正序会多次添加 value[i]
  8.         for j := weight[i]; j <= bagWeight; j++ {
  9.             // 推导公式
  10.             dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
  11.             // debug
  12.             //fmt.Println(dp)
  13.         }
  14.     }
  15.     return dp[bagWeight]
  16. }
  18. // test_CompletePack2 先遍历背包, 在遍历物品
  19. func test_CompletePack2(weight, value []int, bagWeight int) int {
  20.     // 定义dp数组 和初始化
  21.     dp := make([]int, bagWeight+1)
  22.     // 遍历顺序
  23.     // j从0 开始
  24.     for j := 0; j <= bagWeight; j++ {
  25.         for i := 0; i < len(weight); i++ {
  26.             if j >= weight[i] {
  27.                 // 推导公式
  28.                 dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
  29.             }
  30.             // debug
  31.             //fmt.Println(dp)
  32.         }
  33.     }
  34.     return dp[bagWeight]
  35. }
  37. func max(a, b int) int {
  38.     if a > b {
  39.         return a
  40.     }
  41.     return b
  42. }
  44. func main() {
  45.     weight := []int{1, 3, 4}
  46.     price := []int{15, 20, 30}
  47.     fmt.Println(test_CompletePack1(weight, price, 4))
  48.     fmt.Println(test_CompletePack2(weight, price, 4))
  49. }

518. 零钱兑换 II

题目

image.png

思路

本题和纯完全背包不一样，纯完全背包是能否凑成总金额，而本题是要求凑成总金额的个数！
注意题目描述中是凑成总金额的硬币组合数，为什么强调是组合数呢？
例如示例一：
5 = 2 + 2 + 1
5 = 2 + 1 + 2
这是一种组合，都是 2 2 1。
如果问的是排列数，那么上面就是两种排列了。
组合不强调元素之间的顺序，排列强调元素之间的顺序。

回归本题，动规五步曲来分析如下：

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

dp[j]：凑成总金额j的货币组合数为dp[j]

  1. 确定递推公式

dp[j] （coins[i]的组合总和）就是所有的dp[j - coins[i]]（不考虑coins[i]）相加。
所以递推公式：dp[j] += dp[j - coins[i]];
这个递推公式大家应该不陌生了，我在讲解01背包题目的时候在这篇动态规划：目标和！(opens new window)中就讲解了，求装满背包有几种方法，一般公式都是：dp[j] += dp[j - nums[i]];

  1. dp数组如何初始化

首先dp[0]一定要为1，dp[0] = 1是 递归公式的基础。
从dp[i]的含义上来讲就是，凑成总金额0的货币组合数为1。
下标非0的dp[j]初始化为0，这样累计加dp[j - coins[i]]的时候才不会影响真正的dp[j]

  1. 确定遍历顺序

本题中我们是外层for循环遍历物品（钱币），内层for遍历背包（金钱总额），还是外层for遍历背包（金钱总额），内层for循环遍历物品（钱币）呢？
我在动态规划：关于完全背包，你该了解这些！(opens new window)中讲解了完全背包的两个for循环的先后顺序都是可以的。
但本题就不行了！
因为纯完全背包求得是能否凑成总和，和凑成总和的元素有没有顺序没关系，即：有顺序也行，没有顺序也行！
而本题要求凑成总和的组合数，元素之间要求没有顺序。
所以纯完全背包是能凑成总和就行，不用管怎么凑的。
本题是求凑出来的方案个数，且每个方案个数是为组合数。
那么本题，两个for循环的先后顺序可就有说法了。
我们先来看 外层for循环遍历物品（钱币），内层for遍历背包（金钱总额）的情况。

  1. for (int i = 0; i < coins.size(); i++) { // 遍历物品
  2.     for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量
  3.         dp[j] += dp[j - coins[i]];
  4.     }
  5. }

假设：coins[0] = 1，coins[1] = 5。
那么就是先把1加入计算，然后再把5加入计算，得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。所以这种遍历顺序中dp[j]里计算的是组合数！
如果把两个for交换顺序，代码如下：

  1. for (int j = 0; j <= amount; j++) { // 遍历背包容量
  2.     for (int i = 0; i < coins.size(); i++) { // 遍历物品
  3.         if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];
  4.     }
  5. }

背包容量的每一个值，都是经过 1 和 5 的计算，包含了{1, 5} 和 {5, 1}两种情况。
此时dp[j]里算出来的就是排列数！
可能这里很多同学还不是很理解，建议动手把这两种方案的dp数组数值变化打印出来，对比看一看！（实践出真知）

  1. 举例推导dp数组

输入: amount = 5, coins = [1, 2, 5] ，dp状态图如下：
image.png
本题的递推公式，其实我们在动态规划：目标和！(opens new window)中就已经讲过了，而难点在于遍历顺序！
在求装满背包有几种方案的时候，认清遍历顺序是非常关键的。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。

代码

  1. func change(amount int, coins []int) int {
  2.     // 定义dp数组
  3.     dp := make([]int, amount+1)
  4.     // 初始化,0大小的背包, 当然是不装任何东西了, 就是1种方法
  5.     dp[0]  = 1
  6.     // 遍历顺序
  7.     // 遍历物品
  8.     for i := 0 ;i < len(coins);i++ {
  9.         // 遍历背包
  10.         for j:= coins[i] ; j <= amount ;j++ {
  11.             // 推导公式
  12.             dp[j] += dp[j-coins[i]]
  13.         }
  14.     }
  15.     return dp[amount]
  16. }

377. 组合总和 Ⅳ

题目

image.png

思路

首先确定，本题求的就是排列。
dp[i]: 凑成目标正整数为i的排列个数为dp[i]
这里确定递推公式：
dp[ i ]的推导方向，当前物品如果算上了，那dp[ i ] = dp[ i - nums[ j ] ]。如果不算那dp[ i ] = dp[ i ]。
问的是有几种方法，那当前两种情况都要算进去。
求装满背包有几种方法，递推公式一般都是dp[i] += dp[i - nums[j]]两个方向相加。
dp[0] = 1
确定遍历顺序：
个数可以不限使用，说明这是一个完全背包。
得到的集合是排列，说明需要考虑元素之间的顺序。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
如果把遍历nums（物品）放在外循环，遍历target的作为内循环的话，举一个例子：计算dp[4]的时候，结果集只有 {1,3} 这样的集合，不会有{3,1}这样的集合，因为nums遍历放在外层，3只能出现在1后面！
所以本题遍历顺序最终遍历顺序：target（背包）放在外循环，将nums（物品）放在内循环，内循环从前到后遍历。
image.png

代码

  1. func combinationSum4(nums []int, target int) int {
  2.     //定义dp数组
  3.     dp := make([]int, target+1)
  4.     // 初始化
  5.     dp[0] = 1
  6.     // 遍历顺序, 先遍历背包,再循环遍历物品
  7.     for j:=0;j<=target;j++ {
  8.         for i:=0 ;i < len(nums);i++ {
  9.             if j >= nums[i] {
  10.                 dp[j] += dp[j-nums[i]]
  11.             }
  12.         }
  13.     }
  14.     return dp[target]
  15. }

70. 爬楼梯

题目

image.png

思路

改为：一步一个台阶，两个台阶，三个台阶，…….，直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢？
1阶，2阶，…. m阶就是物品，楼顶就是背包。
每一阶可以重复使用，例如跳了1阶，还可以继续跳1阶。
问跳到楼顶有几种方法其实就是问装满背包有几种方法。
dp[i]：爬到有i个台阶的楼顶，有dp[i]种方法。
求装满背包有几种方法，递推公式一般都是dp[i] += dp[i - nums[j]]
本题呢，dp[i]有几种来源，dp[i - 1]，dp[i - 2]，dp[i - 3] 等等，即：dp[i - j]
dp[0] 一定为1

代码

  1. func climbStairs(n int) int {
  2.     //定义
  3.     dp := make([]int, n+1)
  4.     //初始化
  5.     dp[0] = 1
  6.     // 本题物品只有两个1,2
  7.     m := 2
  8.     // 遍历顺序
  9.     for j := 1; j <= n; j++ {    //先遍历背包
  10.         for i := 1; i <= m; i++ {    //再遍历物品
  11.             if j >= i {
  12.                 dp[j] += dp[j-i]
  13.             }
  14.             //fmt.Println(dp)
  15.         }
  16.     }
  17.     return dp[n]
  18. }

322. 零钱兑换

题目

image.png

思路

dp[j]：凑足总额为j所需钱币的最少个数为dp[j]
得到dp[j]（考虑coins[i]），dp[j - coins[i]]（没有考虑coins[i]），凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]，那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j]（考虑coins[i]）
所以dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的。
递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

代码

打家劫舍

198. 打家劫舍

题目

image.png

思路

dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。
如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考虑的，找出 下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。
如果不偷第i房间，那么dp[i] = dp[i - 1]，即考虑i-1房，（注意这里是考虑，并不是一定要偷i-1房，这是很多同学容易混淆的点）
然后dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
初始化：
dp[0] 一定是 nums[0]，dp[1]就是nums[0]和nums[1]的最大值即：dp[1] = max(nums[0], nums[1])

代码

  1. func rob(nums []int) int {
  2.     if len(nums)<1{
  3.         return 0
  4.     }
  5.     if len(nums)==1{
  6.         return nums[0]
  7.     }
  8.     if len(nums)==2{
  9.         return max(nums[0],nums[1])
  10.     }
  11.     dp := make([]int,len(nums))
  12.     dp[0] = nums[0]
  13.     dp[1] = max(nums[0],nums[1])
  14.     for i := 2;i<len(nums);i++{
  15.         dp[i] = max(dp[i-2]+nums[i],dp[i-1])
  16.     }
  17.     return dp[len(nums)-1]
  18. }
  19. func max(a,b int)int{
  20.     if a>b{
  21.         return a
  22.     }
  23.     return b
  24. }

213. 打家劫舍 II

题目

image.png

思路

这道题目和198.打家劫舍(opens new window)是差不多的，唯一区别就是成环了。
对于一个数组，成环的话主要有如下三种情况：

  • 情况一：考虑不包含首尾元素
  • 情况二：考虑包含首元素，不包含尾元素
  • 情况三：考虑包含尾元素，不包含首元素

而情况二 和 情况三 都包含了情况一了，所以只考虑情况二和情况三就可以了。

代码

  1. func rob(nums []int) int {
  2.     if len(nums)<1{
  3.         return 0
  4.     }
  5.     if len(nums)==1{
  6.         return nums[0]
  7.     }
  8.     if len(nums)==2{
  9.         return max(nums[0],nums[1])
  10.     }
  11.     nums1 := nums[1:]
  12.     nums2 := nums[:len(nums)-1]
  13.     a := rob1(nums1)
  14.     b := rob1(nums2)
  15.     return max(a,b)
  16. }
  17. func rob1(nums []int) int {
  19.     if len(nums)==2{
  20.         return max(nums[0],nums[1])
  21.     }
  22.     dp := make([]int,len(nums))
  23.     dp[0] = nums[0]
  24.     dp[1] = max(nums[0],nums[1])
  25.     for i := 2;i<len(nums);i++{
  26.         dp[i] = max(dp[i-2]+nums[i],dp[i-1])
  27.     }
  28.     return dp[len(nums)-1]
  29. }
  30. func max(a,b int)int{
  31.     if a>b{
  32.         return a
  33.     }
  34.     return b
  35. }

337. 打家劫舍 III

题目

image.png
image.png
image.png

思路

本题dp数组就是一个长度为2的数组。
dp数组（dp table）以及下标的含义：下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。
终止条件
如果遇到空节点的话，很明显，无论偷还是不偷都是0，所以就返回
遍历顺序
首先明确的是使用后序遍历。 因为通过递归函数的返回值来做下一步计算。
通过递归左节点，得到左节点偷与不偷的金钱。
通过递归右节点，得到右节点偷与不偷的金钱。

代码

  1. func rob(root *TreeNode) int {
  2.     res := robTree(root)
  3.     return max(res[0], res[1])
  4. }
  6. func max(a, b int) int {
  7.     if a > b {
  8.         return a
  9.     }
  10.     return b
  11. }
  13. func robTree(cur *TreeNode) []int {
  14.     if cur == nil {
  15.         return []int{0, 0}
  16.     }
  17.     // 后序遍历
  18.     left := robTree(cur.Left)
  19.     right := robTree(cur.Right)
  21.     // 考虑去偷当前的屋子
  22.     robCur := cur.Val + left[0] + right[0]
  23.     // 考虑不去偷当前的屋子
  24.     notRobCur := max(left[0], left[1]) + max(right[0], right[1])
  26.     // 注意顺序：0:不偷，1:去偷
  27.     return []int{notRobCur, robCur}
  28. }

121. 买卖股票的最佳时机

题目

image.png
image.png

思路

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

dp[i][0] 表示第i天持有股票所得最多现金
dp[i][1] 表示第i天不持有股票所得最多现金

  1. 确定递推公式

如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来

  • 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
  • 第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]

那么dp[i][0]应该选所得现金最大的，所以dp[i][0] = max(dp[i - 1][0], -prices[i]);
如果第i天不持有股票即dp[i][1]， 也可以由两个状态推出来

  • 第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]
  • 第i天卖出股票，所得现金就是按照今天股票佳价格卖出后所得现金即：prices[i] + dp[i - 1][0]

同样dp[i][1]取最大的，dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
dp[0][0] -= prices[0]
dp[0][1] = 0
从递推公式可以看出dp[i]都是由dp[i - 1]推导出来的，那么一定是从前向后遍历。

代码

  1. func maxProfit(prices []int) int {
  2.     length:=len(prices)
  3.     if length==0{return 0}
  4.     dp:=make([][]int,length)
  5.     for i:=0;i<length;i++{
  6.         dp[i]=make([]int,2)
  7.     }
  9.     dp[0][0]=-prices[0]
  10.     dp[0][1]=0
  11.     for i:=1;i<length;i++{
  12.         dp[i][0]=max(dp[i-1][0],-prices[i])
  13.         dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i])
  14.     }
  15.     return dp[length-1][1]
  16. }
  17. func max(a,b int)int {
  18.     if a>b{
  19.         return a 
  20.     }
  21.     return b 
  22. }