题解 | #换钱的最少货币数#
换钱的最少货币数
http://www.nowcoder.com/practice/3911a20b3f8743058214ceaa099eeb45
经典完全背包问题
- 首先确定背包的遍历顺序直接从外层遍历是物品,里面遍历背包
- 注意是完全背包,一阶dp数组要正向遍历
- 最后注意边界问题
``` java
import java.util.*;
public class Solution {
public int minMoney (int[] arr, int aim){int []dp=new int[aim+1]; Arrays.fill(dp,aim+1);// 初始化最大值的时候直接选取 int n=arr.length; dp[0]=0;//初始状态 for(int a:arr){ for(int j=1;j<=aim;j++){ if(j>=a){ dp[j]=Math.min(dp[j], dp[j - a] + 1); } } } return dp[aim]==aim+1?-1:dp[aim];
}
}