题解 | #兑换零钱(一)#
兑换零钱(一)
https://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 if(aim == 0){ return 0; } // 状态定义:dp[i] 表示组成i的最少货币数 int dp[] = new int[aim + 1]; // 设置每个金额初始值为超出aim目标金额的值,因为面额为正整数,最小为1.因此最后dp[i]>i则表示无解 Arrays.fill(dp,aim + 1); dp[0] = 0; for(int i = 1;i <= aim;i++ ){ for(int j = 0;j < arr.length;j++){ if(arr[j] <= i){ dp[i] = Math.min(dp[i],dp[i - arr[j]] + 1); } } } return dp[aim] > aim?-1:dp[aim]; } }