头脑风暴:零钱兑换 3
题目
给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1:
示例 2:
示例 3:
提示:
1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4
解题思路
根据题意,本题可采用动态规划的方式来求解。
第一步,确定 dp 数组以及下标的含义:
dp[j]:凑足总额为 j 所需钱币的最少个数为 dp[j]。
第二步,确定递推公式:分俩种情况:第一种,dp[j],考虑 coins[i],那只有从 dp[j - coins[i]] 来推导;第二种,凑足总额为 j - coins[i] 的最少个数为 dp[j - coins[i]],那么只需要加上一个钱币 coins[i],表达式为 dp[j - coins[i]] + 1。
所以 dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的。
递推公式为:dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
第三步,dp 数组初始化:
dp[0] = 0。
第四步,确定遍历顺序:
本题求钱币最小个数,那么钱币有顺序和没有顺序都可以,都不影响钱币的最小个数。
代码实现
最后
时间复杂度:O(Sn),其中 S 是金额,n 是面额数。
空间复杂度:O(S)。
版权声明: 本文为 InfoQ 作者【HelloWorld杰少】的原创文章。
原文链接:【http://xie.infoq.cn/article/f700515f407e21ab6c9c15a1f】。文章转载请联系作者。
评论