题解 | #兑换零钱(一)#
兑换零钱(一)
http://www.nowcoder.com/practice/3911a20b3f8743058214ceaa099eeb45
-
就拿给定的例子来说,有5,2,3,三种面值的钱,现在拿出一张20元的,怎么兑换才能使钱的张数最少。
-
首先,我们知道可兑换的钱的最大张数是20,也就是面值是1的时候,其他可兑换的情况张数肯定小于20,那么可兑换张数<=20才是可考虑的范围,且要求最小值。
-
设置的计数数组的长度是比目标钱数还大1的,因为要记录从0到这个目标钱数可兑换的货币张数。
-
这个计数数组的初值均设为比给定钱数还大1,因为可能的最大值是aim,这里设为aim+1,就是为了后面可以更新min,毕竟只要能换,无论怎么换,张数都会比aim+1少。
-
先从小i开始讨论最少换多少张,因为换后面的大i也会用到前面的小i。就是说如果别人拿1,2,3,4,5,6,7,8,9,10来换,你只有面值2,3,5的,那么能不能换开,最少多少张就可以换开。
-
只有在面值比aim小的时候才可以换,换了一张之后,再看余下的钱能不能继续换,直到全部换开,换不开表示的话,dp值就保持初值,能换开就更新最小值
int minMoney(int* arr, int arrLen, int aim ) {
int max = aim + 1; //假设最大值比给的目标值还大1
int dp[max]; //建一个大小为max的数组,表示钱数为i时需要的最少货币张数
for(int i = 0; i < max; i++) //先假设钱数从0到max时均需要max张,后面再求最小值
dp[i] = max;
dp[0] = 0; //显然,0元没有可兑换的
for(int i = 1; i <= aim; i++){ //从1开始算钱数为i时最少需要兑换多少张
for(int j = 0; j < arrLen; j++){ //怎么兑换就是看给定的数组中有没有面值更小的
if(arr[j] <= i) //给定货币的面值有更小的,或者相同的
dp[i] = min(dp[i], dp[i-arr[j]] +1);
//如果有更小的,那么先换一张,然后看余下的钱数还能不能换,依次类推如果能完全兑换,
//那么张数肯定比刚开始假设的max小,毕竟就算全换成1元的,张数也比max小
}
}
return dp[aim] > aim ? -1 : dp[aim]; //要兑换aim的钱,张数最多就是aim张1元的情况,再多就错了,
}