322. 零钱兑换
2 min
题目
解法：动态规划
思路
核心思想是动态规划，通过构建DP数组记录每个金额所需的最少硬币数。
该方法正确是因为每个金额的最优解都依赖于更小金额的最优解，具有最优子结构。通过自底向上计算，确保每个状态都是最优的，且不会遗漏任何可能的硬币组合。
- Step 1: 初始化DP数组，dp[0]=0，其余为amount+1（表示无穷大）
- Step 2: 遍历1到amount每个金额
- Step 3: 对每个硬币面额，尝试使用并更新dp[i]
- Step 4: 返回结果，若dp[amount]未更新则返回-1
复杂度
- 时间复杂度:
- 空间复杂度:
代码
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, amount + 1);
dp[0] = 0;
for(int i = 1; i <= amount; i++){
for(int j = 0; j < coins.size(); j++){
if(i-coins[j] >= 0)
dp[i] = min(dp[i],dp[i-coins[j]]+1);
}
}
return dp[amount] == amount+1 ? -1 : dp[amount];
}
};