C++课程：动态规划第2章 - 背包与硬币组合题

找这个阶段的状态和上各阶段的状态关系
实战！leetcode322

1. 确定状态变量时需考虑硬币数量无限的情况，则状态变量定义为amount。
2. 计算dp[n]时需明确目标金额n所需的最小硬币数量即为dp[n]。
3. 推导状态转移方程时需明确两种情况下的最小值比较，则有递推式 dp[n] = min(dp[n], dp[n - coin] + 1) 表示凑成n元所需的最小硬币数是取两种情况中的较小者。
4. 初始化边界条件时需明确当金额为零时所需硬币数量即为零，则有初始条件 dp[0] = 0 表示凑成零元所需零个硬币。
5. 变量定义如上所述。

    vector<int>  dp(amount+1,amount+1);所有的dp初始值都是amount+1.需要硬币的最大数量+1
    vector<int> coins;

6. 写方程：

    for(int i=0;i<=amount;i++)
    {//dp[i]变量所有的可能性
    	for(int coin:coins) {//在里面循环所有硬币
    	}
    }
    return dp[amount]==amount+1?  看凑amount元需要的硬币数存不存在：不存在则等于初始值（找不到边界）

01背包：每件商品只有一件