题解 | #兑换零钱(一)#

dp=[],代表当总钱数为i时需要的最少钱币数；

假设当前硬币种类为{2,3,5}三种，那么dp[2]=1;dp[3]=1;dp[5]=dp[2]+dp[3];

以此类推的话，dp[6]=min(dp[2]+dp[4],dp[3]+dp[3]}),这时我们可以发现，所谓的球最少硬币数不过是：

令j为硬币集合的下标，i为总钱数；那么便是对j作循环，使得dp[i-j]+dp[j]的和最小（每一项都必须大于0），那么递推公式即为dp[i]=min(dp[i],dp[i-j]+dp[j]),对硬币种类循环完，就得到了当总钱数为i时所需要的最少硬币数。结果返回dp[-1]即可。