题解 | #换钱的最少货币数#

换钱的最少货币数

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];
    }
}
全部评论

相关推荐

04-28 11:34
西北大学 运营
牛客4396号:不好意思,这个照片猛一看像丁真
点赞 评论 收藏
分享
06-06 03:40
已编辑
电子科技大学 Java
在秋招的小白菜很想养修勾:一眼 苍穹外卖+谷粒商城,项目换一换吧,可以找一些付费知识星球博主带带,避免烂大街。多投投大厂,背背八股,你这学历乱杀了,等实习经验到位,到时候大厂闭眼选
投递美团等公司8个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务