代码随想录 day44 第九章 动态规划 part06

动规五部曲

1. dp数组以及下标的含义
2. 递推公式
3. dp数组如何初始化
4. 遍历顺序
5. 打印数组

●  完全背包

●  518. 零钱兑换 II

●  377. 组合总和 Ⅳ

详细布置

力扣上没有纯粹的完全背包的题目，所以大家看本篇了解一下 完全背包的理论

后面的两道题目，都是完全背包的应用，做做感受一下

1. 完全背包

• 完全背包，物品可以无限使用
• 把 01背包 的背包，改成正序遍历
  • 实现物品的多次使用
• 遍历顺序可以颠倒
  • 纯完全背包类问题

2. 零钱兑换 II

关联 leetcode 518. 零钱兑换 II

• 思路

  • 本题要求的是组合数，也就是不考虑 元素顺序
  • 动规五部曲

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

       dp[j] : 装满容量为 j 的背包, 有 dp[j] 种方法
       

    2. 递推公式

       dp[j] += dp[j-coins[i]] // 类似爬楼梯，一个 五阶楼梯，还剩 一节台阶，必须要走到 四阶 的位置
       // 所有方法的累加和
       

    3. dp数组如何初始化

       dp[0] = 1
       

    4. 遍历顺序

       1. 先物品、后背包 顺序
          1. 背包正序遍历

    5. 打印数组

• 题解

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

3. 组合总和 Ⅳ

关联 leetcode 377. 组合总和 Ⅳ

• 思路

  • 本题实际要求的是 排列数，也就是 考虑 元素顺序
  • 动规五部曲

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

       dp[i]: 凑成目标正整数为i的排列个数为dp[i]
       

    2. 递推公式

       dp[j] += dp[j-nums[i]] // 类似爬楼梯，一个 五阶楼梯，还剩 一节台阶，必须要走到 四阶 的位置
       // 所有方法的累加和
       

    3. dp数组如何初始化

       dp[0] = 1 // 其余非零下标初始化为0
       

    4. 遍历顺序

       1. 先背包、后物品 顺序
          1. 物品从前往后

    5. 打印数组

• 题解

  func combinationSum4(nums []int, target int) int {
  	dp := make([]int, target+1)
  	dp[0] = 1
  	for i := 0; i <= target; i++ { //外层背包
  		for j := 0; j < len(nums); j++ { //内层物品
  			if i-nums[j] >= 0 { //背包容量大于当前物品重量
  				dp[i] += dp[i-nums[j]]
  			}
  		}
  	}
  	return dp[target]
  }
  

4. 题外话

在求装满背包有几种方案的时候，认清遍历顺序是非常关键的。

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