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

换钱的最少货币数

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

相关推荐

05-12 22:16
已编辑
北京邮电大学 研发工程师
牛客302360988号:0offer+1 滴滴都不给我面 佬没投鹅吗,鹅应该很喜欢北邮吧
投递美团等公司7个岗位
点赞 评论 收藏
分享
AAA专业长城贴瓷砖刘大爷:这样的简历我会直接丢进垃圾桶,花里胡哨的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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