动态规划-背包

先看动态规划之背包问题系列，以下为重点摘录

动态规划的本质是

从子状态推出当前状态，且无后效性；需要我们合理地定义状态。

最大作用相比dfs避免重复计算

注：本文问题均可进行空间优化，最重要的是模拟填表的思想，子问题推导问题的推导方向，决定了遍历的顺序。比如最长回文子串，dp[l][r]由dp[l+1][r-1])推导得来，应该是如何遍历呢？

01背包

dp[i][j]表示将前i件物品装进限重为j的背包可以获得的最大价值, 0<=i<=N, 0<=j<=W
dp[i][j] = max(dp[i−1][j], dp[i−1][j−w[i]]+v[i]) // j >= w[i]

动态规划的核心思想避免重复计算在01背包问题中体现得淋漓尽致。第i件物品装入或者不装入而获得的最大价值完全可以由前面i-1件物品的最大价值决定

完全背包

完全背包（unbounded knapsack problem）与01背包不同就是每种物品可以有无限多个

dp[i][j] = max(dp[i−1][j], dp[i][j−w[i]]+v[i]) // j >= w[i]
原式：# k为装入第i种物品的件数, k <= j/w[i]
dp[i][j] = max{(dp[i-1][j − k*w[i]] + k*v[i]) for every k}

dp[i][j−w[i]]+v[i]推导：

1. 装入第i种物品，此时和01背包不太一样，因为每种物品有无限个（但注意书包限重是有限的），所以此时不应该转移到dp[i−1][j−w[i]]而应该转移到dp[i][j−w[i]]，即装入第i种商品后还可以再继续装入第种商品。
2. 论证等效性
   

• 与01背包对比
  

恰好装满的非法解思想，求max嘛

多重背包

# k为装入第i种物品的件数, k <= min(n[i], j/w[i])
dp[i][j] = max{(dp[i-1][j − k*w[i]] + k*v[i]) for every k}

常见背包问题

1. 分割等和子集

2. 零钱兑换

3. 零钱兑换II

4. 目标和

5. 一和零

排列组合问题

零钱兑换II和爬楼梯问题到底有什么不同？

1. 不同：爬楼梯1-2和2-1是不同的，而零钱兑换1-2和2-1是相同的

2. 这条评论我觉得说的很好：