欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode322.零钱兑换coinChange

程序员文章站 2022-03-24 20:42:28
...

1、题目描述

LeetCode322.零钱兑换coinChange

2、代码详解

public class coinChange322 {
    public static void main(String[] args){
        int[] coins = {1, 2, 5};
        int amount = 11;
        System.out.println(coinChange(coins, amount));

    }

    public static int coinChange(int[] coins, int amount){
        // 数组大小为 amount + 1,初始值也为 amount + 1
        int max = amount + 1;
        int[] dp = new int[amount+1];
        // base case
        Arrays.fill(dp, max);
        dp[0] = 0;
        for (int i = 0; i <= amount; i++) {//0,<不行,注意边界条件
            // 内层 for 在求所有子问题 + 1 的最小值
            for (int coin : coins) {
                // 子问题无解,跳过
                if (i - coin < 0) continue;
                dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
            }
//            for (int j = 0; j < coins.length; j++) {
//                if (coins[j] <= i) {
//                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
//                }
        }
        return (dp[amount] > amount) ? -1 : dp[amount];
    }
}

labuladong的动态规划

DP法和DFS+greedy+pruning法

https://www.bilibili.com/video/av31621107?from=search&seid=2529841167284044495

相关标签: 动态规划