• LeetCode322:零钱兑换


    要求

    给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。
    计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。

    你可以认为每种硬币的数量是无限的。
    在这里插入图片描述

    思路

    单枚硬币的面值首先要小于等于 当前需要的面值;剩余的面值也要能够凑出来,否则返回-1
    方法一:动态规划
    定义状态:dp[i] :凑齐总价值 i 需要的最少硬币的个数
    状态转移方程:dp[amount] = min(dp[amount], 1 + dp[amount - coins[i]])

    public class LeetCode322 {
        public int coinChange(int[] coins, int amount) {
            //初始赋值不可能的值,当有正常值时,发生转移
            int[] dp = new int[amount + 1];
            //数组dp赋值,这个不可能的值赋值成为最大值
            Arrays.fill(dp,amount+1);
    
            //如果单个值能凑出来符合最优解
            dp[0] = 0;
            //在金额中遍历硬币组合
            for (int i = 1; i <= amount; i++) {
                for (int coin : coins) {
                    //如果金额 - 硬币值大于0 且 dp数组不为不可能的值,寻找最优解
                    if (i - coin >= 0 && dp[i-coin] != amount+1){
                        dp[i] = Math.min(dp[i],dp[i-coin] + 1);
                    }
                }
            }
            //不可能的值
            if (dp[amount] == amount+1){
                return -1;
            }
            return dp[amount];
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    时间复杂度:O(N×amount),这里 N 是可选硬币的种类数,amount是题目输入的面值;
    空间复杂度:O(amount),状态数组的大小为 amount。

    方法二:完全背包
    外层先遍历硬币的面值,内层循环遍历硬币的和

    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
    
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    
        if (dp[amount] == amount + 1) {
            dp[amount] = -1;
        }
        return dp[amount];
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
  • 相关阅读:
    深入解析:微软Edge浏览器的防钓鱼与恶意软件保护机制
    Leetcode 76. 最小覆盖子串
    【Flink】flink简介
    (动态)树分治 学习笔记
    android studio通过wifi、无线连接设备
    如何通过日志的方式理解Redis主从复制
    算法笔记-第十章-图的定义和相关术语
    Windows10安装MySQL5.7.43
    Docker安装部署Redis集群
    【luogu CF633H】Fibonacci-ish II(莫队)(线段树)(矩阵乘法)
  • 原文地址:https://blog.csdn.net/weixin_46426906/article/details/127582706