动态规划

动态规划的五个要点:

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

01 背包

问题模板

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

解答

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

2. 有两个方面:

   1. 不放当前物品, 则 dp[i][j] = dp[i - 1][j];
   2. 放当前物品, 则 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. 初始化:

   1. j = 0 时, 背包容量为 0, 所以 dp[i][0] = 0;

   2. dp[0][j], 即: i 为 0, 存放编号 0 的物品的时候, 各个容量的背包所能存放的最大价值. 所以:

      1. 当 $j<weight$ 的时候, dp[j] 应该是 0, 因为背包容量比编号 0 的物品重量还小;
      2. 当 $j>=weight$ 时, dp[j] 应该是 value[0], 因为背包容量放足够放编号 0 号物品.

   for (int j = 0 ; j < weight[0]; j++) {
       dp[0][j] = 0;
   }
   for (int j = weight[0]; j <= bagWeight; j++) {
    dp[0][j] = 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];
           else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
       }
   }
   

5. 手动模拟测试一下

优化

使用滚动数组将二维数组优化成一维数组

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

2. 依旧是两个方面

   1. 不放当前物品, dp[j] = dp[j]
   2. 放当前物品, dp[j] = dp[j - weight[i]] + value[i]

   所以得出: dp[j]=max(dp[j], dp[j-weight[i]]+value[i])

3. 背包容量为 0 所背的物品的最大价值就是 0, 所以全部初始化为 0 即可

4. 遍历顺序, 这里一定要记住倒序遍历

   因为要保证遍历时 dp[j - weight[i]] 是上一轮遍历得出的值, 如果正序遍历的话, dp[j - weight[i]] 一定会比 dp[j] 先遍历到, 值可能会有改变, 这样就会导致一个物品重复放入背包, 所以要倒序遍历

   for(int i = 0; i < weight.size(); i++) { // 遍历物品
       for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量, j 小于 weight[i] 的值一定不会修改, 就没必要遍历了
           dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
   
       }
   }
   

5. 手动推导测试一下

做题总结

1. 需要转化

   1. 题目中的元素只能用一次;
   2. 题目会有一个上限, 背包的容量就是这个上限

2. 递推公式

   1. 求一共有多少种情况 494.目标和 , 在递推公式中是需要累加

   for i := 0; i < len(nums); i++ {
   	for j := n; j >= nums[i]; j-- {
   		// 如果是求总共有多少情况, 则直接累加
   		dp[j] += dp[j-nums[i]]
   	}
   }
   

   2. 求类似于最大, 最长的结果474.一和零 , 在递推公式中就是普通的比大小取最大值

   for _, c := range cnt01 {
   	for i := m; i >= c[0]; i-- {
   		for j := n; j >= c[1]; j-- {
   			if dp[i-c[0]][j-c[1]]+1 > dp[i][j] {
   				// ! 如果是求最大xxx, 则是比大小然后取最大值
   				dp[i][j] = dp[i-c[0]][j-c[1]] + 1
   			}
   		}
   	}
   }
   

完全背包

问题模板

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

解答

和 01 背包差不多, 不过因为可以无限选取, 所以递推方程变成了 dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i])

// 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][j - weight[i]] + value[i]);
    }
}

优化

用滚动数组优化也是和 01 背包相似, 不过将遍历顺序改为了正序, 因为不用避免重复选取物品的问题

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

    }
}

做题总结

1. 如果求组合数(顺序无关)就是外层 for 循环遍历物品, 内层 for 遍历背包; 如果求排列数(顺序有关)就是外层 for 遍历背包, 内层 for 循环遍历物品

   求组和: 518.零钱兑换 II

   求排列: 377. 组合总和 Ⅳ

   个人理解: 求排列需要在每次更新 dp 数组时保证顺序, 所以要把物品的遍历放到内层循环, 求组合顺序无关就可以把物品的遍历放到外层循环

2. 可以使用类似于 dp[i][0], dp[i][1]... 表示不同状态, 每个状态由上一个状态推出(有点自动机的感觉), 具体可以看股票一系列的题目

3. 定义 dp 数组的时候可以多定义一位, 这样可以避免后续判断负数下标, 例如下面的代码:

   func maxUncrossedLines(nums1 []int, nums2 []int) int {
       m, n := len(nums1), len(nums2)
       // 这里多定义一位
       dp := make([][]int, m+1)
       for i := 0; i <= m; i++ {
       	dp[i] = make([]int, n+1)
       }
   
       ans := 0
       for i := 1; i <= m; i++ {
       	for j := 1; j <= n; j++ {
               // 这里使用 i-1 遍历原数组
               // dp 数组不用判断下标是否大于 0
       		if nums1[i-1] == nums2[j-1] {
       			dp[i][j] = dp[i-1][j-1] + 1
       		} else {
       			dp[i][j] = func(a, b int) int {
       				if a > b {
       					return a
       				} else {
       					return b
       				}
       			}(dp[i-1][j], dp[i][j-1])
       		}
       		if dp[i][j] > ans {
       			ans = dp[i][j]
       		}
       	}
       }
   
       return ans
   }
   

   注意: 这样写的话需要分清 dp[i - 1] 和 nums[i - 1] 的含义, 前一个 i - 1 表示前一个字符, 后者表示当前遍历的字符