确定用作状态转移的dp数组的下标及含义 装满容量j的背包 最少物品是dp[j]
动规核心 状态转移方程/递推公式
dp数组如何初始化
class Solution {
public:
int coinChange(std::vector<int>& coins, int amount) {
// 设置成INT_MAX-1 防止dp[j-coins[i]]+1 整数越界
std::vector<int> dp(amount+1, INT_MAX-1); // dp数组长度对应背包大小
dp[0] =0;
for (int i=0;i<coins.size();i++) //遍历物品
// 此处j不能从1开始，避免dp[j-coins[i]]下标负数
for (int j=coins[i];j <= amount;j++) //遍历背包
// +1因为上个背包到当前背包多加了一个物品 当前背包加不同物品i 会产生多个dp[j] 求最小
dp[j] = std::min(dp[j-coins[i]]+1, dp[j]);
if (dp[amount]==INT_MAX-1) return -1;
return dp[amount];
}
};