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

换钱的最少货币数

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

相关推荐

Southyeung:我说一下我的看法(有冒犯实属抱歉):(1)简历不太美观,给我一种看都不想看的感觉,感觉字体还是排版问题;(2)numpy就一个基础包,机器学习算法是什么鬼?我感觉你把svm那些写上去都要好一点。(2)课程不要写,没人看,换成获奖经历;(3)项目太少了,至少2-3个,是在不行把网上学习的也写上去。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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