动态规划的核心是穷举
动态规划问题的一般形式就是求最值
明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义
确定「状态」，也就是原问题和子问题中会变化的变量。
确定「选择」，也就是导致「状态」产生变化的行为。
通常，对于一些明显不是「增加维度」的新限制条件，我们应当考虑直接将其拎出讨论，而不是多增加一维进行状态记录
# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
for 状态2 in 状态2的所有取值：
for ...
dp[状态1][状态2][...] = 求最值(选择1，选择2...)01背包第二个循环逆序的原因
for (int i = 1; i <= n; i++)
for (int j = V; j >= w[i]; j--)
f[j] = max(f[j], f[j - w[i]] + v[i]);从上面可以看到，对v来说，它是从V递减到Ci的，而且一定只能是逆序，这是因为：
从内循环来说，每一次内循环，都相当于更新在i下，背包容量为v最优解。更新之前，F[v]表示i-1下的最优解，而一旦赋值结束，F[v]就表示i下的最优解了。
如果为顺序，当我们进行到F[v]时，要使用到F[v-Ci]，但是这个F[v-Ci]必须是i-1下的最优解，而由于顺序的原因，在我们将v递增到（顺序的情况下）v时，已经经历了v-Ci这个背包容量了，换句话说，此时v下的F[v-Ci]，已经代表的是i下背包容量为v-Ci的最优解了，而我们需要的是i-1下，背包容量为v-Ci的最优解！
因此，我们必须要使用逆序，这样当进行到v时，F[v-Ci]还未更新，它还依然表示i-1下的最优解。
完全背包循环顺序问题
求组合数（比如2，1和1，2只算一个，不重复）代码如下：
for (int i = 0; i < coins.size(); i++) { // 遍历物品
for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量
dp[j] += dp[j - coins[i]];
}
}排列数（重复）：
for (int j = 0; j <= amount; j++) { // 遍历背包容量
for (int i = 0; i < coins.size(); i++) { // 遍历物品
if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];
}
}熟悉套路
322. 零钱兑换
class Solution {
public int coinChange(int[] coins, int amount) {
//自顶向下
int[] memo =new int[amount+1];
Arrays.fill(memo,-666);
return dp(coins,memo,amount);
}
public int dp(int[] coins,int[] memo,int amount){
//base case
if(amount < 0){
return -1;
}
if(amount == 0){
return 0;
}
//备忘录里有的话直接返回
if(memo[amount] != -666){
return memo[amount];
}
int res = Integer.MAX_VALUE;
//穷举状态
for(int coin : coins){
int subProblem = dp(coins,memo,amount - coin);
if(subProblem == -1){
continue;
}
//选择
res = Math.min(res,subProblem + 1);
}
//看看金额amount能不能凑出来
memo[amount] = res == Integer.MAX_VALUE? -1 : res;
return memo[amount];
}
}class Solution {
public int coinChange(int[] coins, int amount) {
//因为选择取最小，dp全部初始化为比最大值大
int[] dp = new int[amount+1];
Arrays.fill(dp,amount + 1);
//base case
dp[0] = 0;
//置底向上遍历
for(int i = 1; i < dp.length; ++i){
for(int coin : coins){
if(i >= coin){
int temp = dp[i - coin];
dp[i] = Math.min(dp[i],temp + 1);
}
}
}
return dp[amount] == amount + 1? -1 : dp[amount];
}
}72. 编辑距离
dp[i][j]代表 word1 到 i 位置转换成 word2 到 j 位置需要最少步数
所以，
当 word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]；
当 word1[i] != word2[j]，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
其中，dp[i-1][j-1]表示替换操作，dp[i-1][j]表示删除操作，dp[i][j-1]表示插入操作。
注意，针对第一行，第一列要单独考虑，我们引入 ‘ ‘ 下图所示：
第一行，是 word1 为空变成 word2 最少步数，就是插入操作
第一列，是 word2 为空，需要的最少步数，就是删除操作
class Solution {
public int minDistance(String word1, String word2) {
int len1 = word1.length();
int len2 = word2.length();
int[][] dp = new int[len1 + 1][len2 + 1];
//base case
for(int i = 0 ; i <=len2; ++i){
dp[0][i] = i;
}
for(int i = 1; i <= len1; ++i){
dp[i][0] = i;
}
//穷举状态
for(int i = 1; i <= len1; ++i){
for(int j = 1; j <= len2; ++j){
if(word1.charAt(i-1) == word2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1];
}else{
//选择
dp[i][j] = Math.min(dp[i-1][j],Math.min(dp[i][j-1],dp[i-1][j-1])) + 1;
}
}
}
return dp[len1][len2];
}
}516. 最长回文子序列
//反着遍历
class Solution {
public int longestPalindromeSubseq(String s) {
int len = s.length();
int[][] dp = new int[len][len];
//初始化对角线为1，base case
for(int i = 0; i < len; ++i){
dp[i][i] = 1;
}
for(int i = len - 1; i >= 0; --i){
for(int j = i + 1; j < len; ++j){
if(s.charAt(i) == s.charAt(j)){
dp[i][j] = dp[i+1][j-1] + 2;
}else{
dp[i][j] = Math.max(dp[i][j-1],dp[i+1][j]);
}
}
}
return dp[0][len-1];
}
}
//斜着遍历
class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[][] dp = new int[n][n];
for(int i = 0; i < n; i++)dp[i][i] = 1;
for(int len = 1; len <= n; len++){
for(int i = 0; i < n - len; i++){
int j = i + len;
if(s.charAt(i) == s.charAt(j)){
dp[i][j] = dp[i + 1][j - 1] + 2;
}else dp[i][j] = Math.max(dp[i + 1][j],dp[i][j - 1]);
}
}
return dp[0][n - 1];
}
}01背包
只考虑第 i 件物品的策略
f[i][j]=max(f[i−1][j],f[i−1][j−w[i]]+v[i])
for (int i = 1; i <= n; i++)
for (int j = V; j >= w[i]; j--)
f[j] = max(f[j], f[j - w[i]] + v[i]);初始化的细节
有的题目要求”恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。这两种问法的区别是在初始化的时候有所不同。
如果是第一种问法，要求恰好装满背包，那么在初始化时除了f [ 0 ]为0其它f [ 1… V ]均设为− ∞，这样就可以保证最终得到的f [ N ]是一种恰好装满背包的最优解。
如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f [ 0… V ]全部设为0。
为什么呢？可以这样理解：初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的n o t h i n g“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是− ∞了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。这个小技巧完全可以推广到其它类型的背包问题，后面也就不再对进行状态转移之前的初始化进行讲解。
完全背包
f[i][j]=max(f[i−1][j−k∗w[i]]+k∗v[i])∣0<=k∗w[i]<=j优化
若两件物品i、j满足w [ i ] < = w [ j ] 且v [ i ] > = v [ j ]，则将物品j去掉，不用考虑。
首先将费用大于V的物品去掉，然后使用类似计数排序的做法，计算出费用相同的物品中价值最高的是哪个，可以O ( V + N )地完成这个优化
转化为01背包
for (int i = 1; i <= n; i++)
for (int j = w[i]; j <= V; j++)
f[j] = max(f[j], f[j - w[i]] + v[i]);
//等价于
f[i][j]=max(f[i−1][j],f[i][j−w[i]]+v[i])排列数和组合数
零钱兑换II：给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
一开始我是这样写的，定义子问题: problem(i) = sum( problem(i-j) ), j =1,2,5. 含义为凑成总金额i的硬币组合数等于凑成总金额硬币i-1, i-2, i-5,…的子问题之和。
dp[0] = 1;
for (int j = 1; j <= amount; j++){ //枚举金额
for (int i = 0; i < coins.size(): i++){
int coin = coins[i]; //枚举硬币
if (j < coin) continue; // coin不能大于amount
dp[j] += dp[j-coin];
}
}但是当你运行之后，却发现这个代码并不正确，得到的结果比预期的大。究其原因，该代码计算的结果是排列数，而不是组合数，也就是代码会把1,2和2,1当做两种情况。但更加根本的原因是我们子问题定义出现了错误。
排列数dp：
| coin\amount | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 2 | 3 | 5 |
| 2 | 1 | 1 | 2 | 2 | ||
| 5 | 1 |
组合数dp：
| coin\amount | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 1 | 1 | 2 | 2 | ||
| 5 | 1 |
正确的子问题定义应该是，problem(k,i) = problem(k-1, i) + problem(k, i-k)
即前k个硬币凑齐金额i的组合数等于前k-1个硬币凑齐金额i的组合数加上在原来i-k的基础上使用硬币的组合数。说的更加直白一点，那就是用前k的硬币凑齐金额i，要分为两种情况开率，一种是没有用前k-1个硬币就凑齐了，一种是前面已经凑到了i-k，现在就差第k个硬币了。
这是个组合问题，我们不关心硬币使用的顺序，而是硬币有没有被用到。是否使用第k个硬币受到之前情况的影响。
class Solution {
public int change(int amount, int[] coins) {
int n = coins.length;
int[] dp = new int[amount + 1];
dp[0] = 1;
for(int i = 0; i < n; i++){
for(int j = coins[i]; j <= amount; j++){
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
}子序列默认不连续，子数组默认连续
多重背包
f[i][j]=max(f[i−1][j−k∗w[i]]+k∗v[i])∣0<=k<=p[i]
for (int i = 1; i <= n; i++) {
int num = min(p[i], V / w[i]);
for (int k = 1; num > 0; k <<= 1) {
if (k > num) k = num;
num -= k;
for (int j = V; j >= w[i] * k; j--)
f[j] = max(f[j], f[j - w[i] * k] + v[i] * k);
}
}背包问题问法变化
输出方案
再用一个数组g [ i ] [ j ]，设g [ i ] [ j ] = 0表示推出f [ i ] [ j ]的值时是采用了方程的前一项（也即f [ i ] [ j ] = f [ i − 1 ] [ j ] ），g [ i ] [ j ] = 1表示采用了方程的后一项。注意这两项分别表示了两种策略：未选第i个物品及选了第i个物品，最终状态为f [ N ] [ V ] 。
求方案总数
对于一个给定了背包容量、物品费用、物品间相互关系（分组、依赖等）的背包问题，除了再给定每个物品的价值后求可得到的最大价值外，还可以得到装满背包或将背包装至某一指定容量的方案总数。对于一个给定了背包容量、物品费用、物品间相互关系（分组、依赖等）的背包问题，除了再给定每个物品的价值后求可得到的最大价值外，还可以得到装满背包或将背包装至某一指定容量的方案总数。对于这类改变问法的问题，一般只需将状态转移方程中的m a x改成s u m即可。例如若每件物品均是完全背包中的物品，转移方程即为
f[i][j]=∑f[i−1][j],f[i][j−w[i]]初始条件f [ 0 ] [ 0 ] = 1。事实上，这样做可行的原因在于状态转移方程已经考察了所有可能的背包组成方案。
最优方案的总数
这里的最优方案是指物品总价值最大的方案。以01背包为例。
结合求最大总价值和方案总数两个问题的思路，最优方案的总数可以这样求：f [ i ] [ j ]意义同前述，g [ i ] [ j ]表示这个子问题的最优方案的总数，则在求f [ i ] [ j ]的同时求g [ i ] [ j ]
背包问题的搜索解法
搜索的剪枝
基本的剪枝方法不外乎可行性剪枝或最优性剪枝。
可行性剪枝即判断按照当前的搜索路径搜下去能否找到一个可行解，例如：若将剩下所有物品都放入背包仍然无法将背包充满（设题目要求必须将背包充满），则剪枝。
最优性剪枝即判断按照当前的搜索路径搜下去能否找到一个最优解，例如：若加上剩下所有物品的权值也无法得到比当前得到的最优解更优的解，则剪枝。
搜索的顺序
在搜索中，可以认为顺序靠前的物品会被优先考虑。
所以利用贪心的思想，将更有可能出现在结果中的物品的顺序提前，可以较快地得出贪心地较优解，更有利于最优性剪枝。所以，可以考虑将按照“性价比”（权值/费用）来排列搜索顺序。
另一方面，若将费用较大的物品排列在前面，可以较快地填满背包，有利于可行性剪枝。
最后一种可以考虑的方案是：在开始搜索前将输入文件中给定的物品的顺序随机打乱。这样可以避免命题人故意设置的陷阱。
以上三种决定搜索顺序的方法很难说哪种更好，事实上每种方法都有适用的题目和数据，也有可能将它们在某种程度上混合使用。
搜索还是D P
首先，可以从数据范围中得到命题人意图的线索。如果一个背包问题可以用D P解，V一定不能很大，否则O （ V N ）的算法无法承受，而一般的搜索解法都是仅与N有关，与V 无关的。所以，V 很大时（例如上百万），命题人的意图就应该是考察搜索。另一方面，N较大时（例如上百），命题人的意图就很有可能是考察动态规划了。另外，当想不出合适的动态规划算法时，就只能用搜索了。例如看到一个从未见过的背包中物品的限制条件，无法想出D P的方程，只好写搜索以谋求一定的分数了。
