力扣 | 322. 零钱兑换

2024-01-10 13:00:02

在这里插入图片描述

这里使用动态规划,代码简洁更易理解

package _322;

import java.util.Arrays;

public class Problem_322_CoinChange {
    public int coinChange(int [] conins,int amount){
        //1. 状态定义,dp[i]表示凑齐金额为i的时候的最小硬币数量
        int dp [] = new int[amount + 1];
        //2. 状态初始化,因为比较的是最小值,所以不可能比总金额数更大
        Arrays.fill(dp,amount + 1);//或者初始化为Math.MAXVALUE;
        //凑齐总金额数为 0 的时候的硬币数量就是不选硬币
        dp[0] = 0;
        //3. 状态转移
        for (int i = 0; i < conins.length; i++) {
            for (int c = conins[i]; c <= amount; c++) {
                dp[c] = Math.min(dp[c],1 + dp[c - conins[i]]);
            }
        }
        //4. 返回最终需要的状态值
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }
}

文章来源:https://blog.csdn.net/qq_37247026/article/details/135495469
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。