题解 | #兑换零钱(一)#
兑换零钱(一)
http://www.nowcoder.com/practice/3911a20b3f8743058214ceaa099eeb45
思路：利用动态规划法，设置数组dp，每一个元素dp[i]的值表示i元钱的最小兑换数目，但如果是aim+1则说明无法兑换；对dp除第一个元素每个遍历，依次和arr的每个元素（每种面值的钱）比对，可兑换则加一次兑换次数；最后输出最少兑换次数。
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
if (arr.length==0) //特殊情况处理
return -1;
int[] dp = new int[aim+1]; //设置数组dp，每一个元素dp[i]的值表示i元钱的最小兑换数目
for (int i = 1; i<=aim; i++) {
dp[i] = aim+1; //判断用
for (int j = 0; j<arr.length; j++) { //依次对arr的每个元素（每种面值）比对
if (i>=arr[j])
dp[i] = Math.min(dp[i], dp[i-arr[j]]+1); //求最小值，其中“+1”得到含义是兑换零钱的次数加一
}
}
return dp[aim]>aim? -1: dp[aim]; //如果dp[aim]的值仍为aim+1则说明无法兑换；反之输出最少兑换次数
}
}
投递拼多多集团-PDD等公司10个岗位