动态规划

动态规划的五个要点:

  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]]
	}
}
    1. 求类似于最大, 最长的结果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 表示前一个字符, 后者表示当前遍历的字符