动态规划笔记

完全背包

完全背包指的是物品可重复使用

物品外循环,背包内循环

for (int i = 0; i < coins.size(); i++) { // 遍历物品（硬币）for (int j = coins[i]; j <= amount; j++) { // 遍历背包（金额），从小到大// 状态转移：使用当前硬币coins[i]更新金额j的最小硬币数}
}

-核心逻辑: 逐个处理每个硬币,对于每个硬币,更新所有可能的背包容量(金额)
-重复选择的逻辑在哪: 背包遍历的顺序是从小到大,当处理物品coins[i]时,状态dp[j-coins[i]]时已经处理过的状态,包含coins[i]的使用,因此允许重复使用同一物品

举例:处理硬币2时,计算dp[4]时候的状态会用到dp[2],这时候已经包含了硬币2的使用,实现了重复使用

背包外循环,物品内循环

for (int j = 1; j <= amount; j++) { // 遍历背包（金额）for (int i = 0; i < coins.size(); i++) { // 遍历物品（硬币）if (j >= coins[i] && dp[j - coins[i]] != INT_MAX) {dp[j] = min(dp[j], dp[j - coins[i]] + 1);}}
}

• 核心逻辑: 逐个处理背包容量,对于每个容量,尝试使用所有物品进行更新.
• 重复选择的实现: 背包遍历顺序是从小到大,因此处理容量j时,物品coins[i]的多次使用会被自动处理.例如:
  用硬币1时,j-1=3的状态已经包含了硬币1的多次使用
  用硬币2时,j-2=2的状态已经包括了硬币2的使用

01背包

物品外循环,背包内循环

for (int i = 0; i < items.size(); i++) { // 物品外循环for (int j = amount; j >= items[i]; j--) { // 背包从大到小dp[j] = min(dp[j], dp[j - items[i]] + 1); // 避免重复选同一物品}
}

要注意的是,这里的背包遍历,是从大到小,理由:
如果是从小到大遍历,j-items[i]的状态是当前物品处理过的状态,会导致同一物品被多次选择,从大到小遍历可以保证每个物品仅影响后续更大的背包容量,实现仅选一次

物品内循环,背包外循环

不行,这样背包从小到大也无法做到物品仅仅选一次,因为背包会容量会遍历所有物品,导致重复计算