背包题目

01背包：416. 分割等和子集 474. 一和零 494. 目标和 879. 盈利计划 1049. 最后一块石头的重量 II 1230. 抛掷硬币
完全背包：1449. 数位成本和为目标值的最大数字 322. 零钱兑换 518. 零钱兑换 II 279. 完全平方数

参考文章

一篇文章吃透背包问题！（细致引入+解题模板+例题分析+代码呈现）

动态规划基本知识

动态规划五部曲：

• 确定dp数组 (dp table) 以及下标的含义
• 确定递推公式
• dp数组如何初始化
• 确定遍历顺序

• 举例推导dp数组

  0-1背包

  第一步要明确两点，「状态」和「选择」

• 状态有两个，就是「背包的容量」和「可选择的物品」。

• 选择就是「装进背包」或者「不装进背包」。

  for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for...
            dp[状态1][状态2][...] = 择优（选择1，选择2...）

  第二步要明确dp数组的定义

  0-1背包问题状态有2个，因此dp数组是一个二维数组。
  dp[i][w]的定义如下：对于前i个物品，当前背包的容量为w，这种情况下可以装的最大价值是dp[i][w]。这样定义是为了便于状态转移。
  根据这个定义，我们想求的最终答案就是dp[N][W]。base case就是dp[0][...] = dp[...][0] = 0。因为没有物品或者背包没有空间的时候，能装的最大价值就是0。 ```json int[][] dp[N+1][W+1] dp[0][…] = 0 dp[…][0] = 0

for i in [1…N]: for w in [1…W]: dp[i][w] = max( 把物品i装进背包， 不把物品i装进背包 ) return dp[N][W]

<a name="UeSb8"></a>
### 第三步根据「选择」思考「状态转移」的逻辑
用代码体现「把物品i装进背包」和「不把物品i装进背包」。<br />`dp[i][w]`表示：对于前`i`个物品，当前背包的容量为`w`时，这种情况下可以装下的最大价值是`dp[i][w]`。<br />如果不把第`i`个物品装入背包，那么很显然，最大价值`dp[i][w]`应该等于`dp[i-1][w]`，继承之前的结果。<br />如果把第i个物品装入背包，那么`dp[i][w]`应该等于`dp[i-1][w - wt[i-1]] + val[i-1]`。<br />由于`i`是从1开始的，所以`val`和`wt`的索引是`i-1`时表示第`i`个物品的价值和重量。<br />如果装了第`i`个物品，就要寻求剩余重量`w-wt[i-1]`限制下的最大价值，加上第`i`个物品的价值`val[i-1]`。
```json
for i in [1...N]:
    for w in [1...W]:
        dp[i][w] = max(
      dp[i-1][w],
      dp[i-1][w - wt[i-1]] + val[i-1]
    )
return dp[N][W]

动态规划题目

746. 使用最小花费爬楼梯

到楼梯顶部的那一步没有花费，但是为了到达楼梯顶部，dp数组的长度需要为l1+1。

198. 打家劫舍

• 适当扩大dp数组长度
• 注意数组前后是否能取到，比如此题就是可能偷倒数第一家就结束战斗，也可能偷倒数第二家结束。

DP五部曲分析：

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

dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。

1. 确定递推公式

决定dp[i]的因素就是第i间房偷还是不偷。

1. dp数组如何初始化
2. 确定遍历顺序
3. 举例推导dp数组

   213. 打家劫舍II

• 房屋围成一圈，所以第一家和最后一家只能偷一个

0-1背包表格记录

目标和背包表格