01 背包

给你一个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。其中第 i 个物品的重量为 wt[i]，价值为 val[i]，现在让你用这个背包装物品，最多能装的价值是多少？
框架

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

明确 DP 数组的含义：

dp[i][w] 的定义如下：对于前 i 个物品，当前背包的容量为 w，这种情况下可以装的最大价值是 dp[i][w]。

比如 dp[3][5] = 6 的含义是：对于给定的一系列物品中，若只对前 3 个物品进行选择，当背包容量为 5 时，所能装入最大物品价值为 6。
状态转移：如果你没有把这第 i 个物品装入背包，那么很显然，它的最大价值 dp[i][w] = dp[i-1][w]。
如果你把这第 i 个物品装入背包，那么 dp[i][w] = dp[i-1][w- wt[i-1]] + val[i-1]。

首先，i 是从 1 开始的，所以 wt 和 val 的取值是 i-1。
dp[i-1][w- wt[i-1]] 公式的理解是：如果你想装入第 i 个物品，那么需要在能装第 i 个物品的前提下，背包所能装的最大价值。显然，我们应该寻求剩余重量 w - wt[i - 1] 限制下能装的最大价值，加上第 i 个物品的价值 val[i-1]。

Base Case：dp[0][…]：没有物品或背包没有空间的时候，能装的最大价值就是 0。

「力扣」上的 0-1 背包问题：
「力扣」第 416 题：分割等和子集（中等）；
「力扣」第 474 题：一和零（中等）；
「力扣」第 494 题：目标和（中等）；
「力扣」第 879 题：盈利计划（困难）；
「力扣」上的完全背包问题：

「力扣」第 322 题：零钱兑换（中等）；
「力扣」第 518 题：零钱兑换 II（中等）；
「力扣」第 1449 题：数位成本和为目标值的最大数字（困难）。
这里要注意鉴别：「力扣」第 377 题，不是「完全背包」问题。

完全背包

有一个背包，最大容量为 amount，有一系列物品 coins，每个物品的重量为 coins[i]，物品数量无限制。请问有多少种方法，能够把背包恰好装满 ?
状态转移方程：如果不把第 i 个物品放入背包，凑出背包容量为 j 的方法数应该为 dp[i-1][j]。如果你把第 i 个物品装入背包，那么 dp[i][j] = dp[i][j - coins[i - 1]]。这里就和 01 背包出现分岐，对于完全背包也很好理解，当我们决定使用第 i 个物品，我们只需要关注如何凑出 j - coins[i - 1] ，物品数量不再限制我们，我们不再需要从 0 ~ i-1中选出最大值，而是从 0 ~ i 选出。

排列/组合

class Solution1 {
public:
    int change(int amount, vector<int>& coins) {
        int dp[amount+1];
        memset(dp, 0, sizeof(dp)); //初始化数组为0
        dp[0] = 1;
        for (int j = 1; j <= amount; j++){ //枚举金额
            for (int coin : coins){ //枚举硬币
                if (j < coin) continue; // coin不能大于amount
                dp[j] += dp[j-coin];
            }
        }
        return dp[amount];
    }
};
class Solution2 {
public:
    int change(int amount, vector<int>& coins) {
        int dp[amount+1];
        memset(dp, 0, sizeof(dp)); //初始化数组为0
        dp[0] = 1;
        for (int coin : coins){ //枚举硬币
            for (int j = 1; j <= amount; j++){ //枚举金额
                if (j < coin) continue; // coin不能大于amount
                dp[j] += dp[j-coin];
            }
        }
        return dp[amount];
    }
};

枚举硬币是组合。1, 2 和 2, 1 是一种情况。组合问题我们不关心使用顺序，而是关心硬币有没有被用到。

枚举金额是排列。1, 2 和 2, 1 是两种情况。

爬楼梯泛化

可以上 1、2 阶：

class Solution {
public:
 int climbStairs(int n) {
     int DP[n+1];
     memset(DP, 0, sizeof(DP));
     DP[0] = 1;
     int steps[2] = {1,2};
     for (int i = 1; i <= n; i++){
         for (int j = 0; j < 2; j++){
             int step = steps[j];
             if ( i < step ) continue;// 台阶少于跨越的步数
             DP[i] = DP[i] + DP[i-step];
         }
     }
     return DP[n];

 }
};

那如果可以上 4、5、6 呢 ?

class Solution {
public:
 int climbStairs(int n) {
     int DP[n+1];
     memset(DP, 0, sizeof(DP));
     DP[0] = 1;
     int steps[2] = {1,2};
     for (int i = 1; i <= n; i++){
         for (int j = 0; j < 2; j++){
             int step = steps[j];
             if ( i < step ) continue;// 台阶少于跨越的步数
             DP[i] = DP[i] + DP[i-step];
         }
     }
     return DP[n];

 }
};

显然不能，因为我们这里定义的子问题是，必须选择第 k 个硬币时，凑成金额 i 的方案。如果交换了，我们的子问题就变了，那就是对于金额 i, 我们选择硬币的方案。