题解 | #换钱的最少货币数#
换钱的最少货币数
http://www.nowcoder.com/practice/3911a20b3f8743058214ceaa099eeb45
import java.util.*;
public class Solution {
/**
* 最少货币数
* @param arr int整型一维数组 the array
* @param aim int整型 the target
* @return int整型
*/
public int minMoney (int[] arr, int aim) {
// write code here
int length = arr.length;
if(length == 0){//空数组处理
return -1;
}
int[] dp = new int[aim+1];//创建一个动态规划dp数组,dp[i]表示兑换面额为i的最少货币数量。
Arrays.fill(dp,aim+1);//初始化dp数组为最大值(根据题意可以是大于aim的任意整数)
dp[0] = 0;//换面额为0的最少货币数量位0
for(int i=1;i<=aim;i++){//迭代更新dp[i]数组
for(int j = 0;j<length;j++){//遍历所有面额值
if(i>=arr[j]){
//动态规划关系式,dp[i] = min(dp[i], dp[i-arr[j]] +1);,利用前面已经求得的数据(dp[i-arr[j]])更新dp[i]
dp[i] = Math.min(dp[i],dp[i-arr[j]]+1);
}
}
}
//返回值,如果dp[aim]>aim表示不能兑换,反之可以兑换,且最少兑换货币数量为dp[aim]
return dp[aim]>aim?-1:dp[aim];
}
}