LeetCode:322. 零钱兑换——动态规划从案例入门

简介: 题目描述:给你一个整数数组coins,表示不同面额的硬币;以及一个整数 amount,表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回-1。你可以认为每种硬币的数量是无限的。

🍎道阻且长,行则将至。🍓


🌻算法,不如说它是一种思考方式🍀


算法专栏: 👉🏻123


一、🌱322. 零钱兑换

  • 题目描述:给你一个整数数组coins,表示不同面额的硬币;以及一个整数 amount,表示总金额。计算并返回可以凑成总金额所需的==最少的硬币个数==。如果没有任何一种硬币组合能组成总金额,返回-1。你可以认为每种硬币的数量是无限的。
  • 来源:力扣(LeetCode)
  • 难度:中等
  • 提示:

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

  • 示例 1:

输入:coins = [1, 2, 5], amount = 11
输出:3
解释:11 = 5 + 5 + 1
示例 2:
输入:coins = [2], amount = 3
输出:-1
示例 3:
输入:coins = [1], amount = 0
输出:0

🌾动态规划

动态规划实质上是一种以空间换时间的技术,它在实现的过程中,不得不存储产生过程中的各种状态,所以它的空间复杂度要大于其他的算法。
  • 先不考虑动态规划来看这道题:就是求解一个最优组合使得最少个数达到总金额目标。

我们最容易想到就是去暴力求解,就是找出所有合适的组合,确定一个最小的。以示例1来看【==coins = [1, 2, 5], amount = 11==】,3个硬币那我们套三层循环,总可以遍历出来的。但是当这个amout非常大呢、硬币数量非常多的时候,这总时间开销会非常大,指数级别了。

  • 那么这时候换一个思路:我们要求出最后完成amout,那我们看最后一枚硬币假如是c~k~,这个c~k~就会有3种可能取值:1,2,5。

假如我们设置一个函数来求解最少需要用多少枚硬币凑出x:f(x)。
那么当c~k~=1,f(11)=f(10)+1;——就是当最后一枚硬币是1,那我们就要进一步求如何最小的凑出10;
那么当c~k~=2,f(11)=f(9) + 1;——就是当最后一枚硬币是2,那我们就要进一步求如何最小的凑出9;
那么当c~k~=5,f(11)=f(6) + 1;——就是当最后一枚硬币是5,那我们就要进一步求如何最小的凑出6;
这时候我们发现上面就是:f(11)=min{f(10)+1,f(9) + 1,f(6) + 1},后面也是类似的过程,于是我们可以写出一个递归实现的方法:跳转到递归实现。👇🏻

  • 但是递归实现仍然时间复杂度太高,我们继续上面的推一下就会发现,里面存在大量重复计算,例如在计算f(10)又会出现f(9)...

还是对于f(11)=min{f(10)+1,f(9) + 1,f(6) + 1},我们可以写为f(x)=min{f(x-1)+1,f(x-2) + 1,f(x-5) + 1}。我们把f看为数组,把每一个amout看为下标,
❶amount当然不能小于0,那小于0的暂设置为无穷大吧,
❷f(0)就代表凑0元,那么就只有0枚,
❸f(1)就代表凑1元,根据f(x),计算是1
...

0 1 2 3 ...
0 1 1 2 ...

这样计算方程的时候,后面的直接使用数组前面已计算的,就不会造成重复计算了。
上面的过程我们就完成了确定状态、状态转移方程、初始化、递推求解。跳转到动态规划实现。👇🏻

动态规划算法思想

通常用于解决具有重叠子问题和最优子结构性质的问题。动态规划算法的思想是将原问题拆解成若干个子问题,通过求解子问题的最优解来求解原问题的最优解。
动态规划算法一般分为以下几个步骤:

  1. 确定状态:将原问题拆解成若干个子问题,确定状态,状态表示的是原问题和子问题中的变量。
  2. 确定状态转移方程:根据子问题和原问题之间的关系,确定状态转移方程,状态转移方程表示的是子问题之间的关系。
  3. 初始化:确定初始状态,即==最小的子问题的解==。
  4. 递推求解:按照状态转移方程,从==初始状态==开始逐步求解子问题,直到求解出原问题的最优解。

动态规划算法的优点是可以避免重复计算,大大提高了算法的效率。动态规划算法可以解决很多问题,如最长公共子序列、背包问题、最短路径问题等。

状态转移方程

状态转移方程是动态规划算法的核心,是求解最优子结构问题的重要手段。其实质是将问题从大到小分解为若干个子问题,然后根据子问题之间的关系,通过递推的方式求解出原问题的最优解。
状态转移方程的一般形式为:
dp[i] = f(dp[i-1], dp[i-2], ..., dp[0])
其中,dp[i]表示原问题中规模为i的问题的解,f为求解dp[i]的函数,dp[0]到dp[i-1]表示规模比i小的子问题的解。状态转移方程的求解需要满足以下条件:

  1. 问题具有最优子结构性质,即原问题的最优解可以由子问题的最优解递推得到。
  2. 问题具有重叠子问题性质,即子问题之间存在重叠,同一个子问题可能被多次求解。

状态转移方程的求解通常需要一定的数学分析能力和算法设计能力,需要根据问题的特点和规模,选择合适的递推方式和边界条件,确保算法的正确性和高效性。常见的状态转移方程包括斐波那契数列、最长公共子序列、背包问题等,这些问题的状态转移方程都具有简单明了的形式和良好的递推性质,是动态规划算法的经典例题。

  • 以斐波那契数列(==从第三项开始,每一项都等于前两项之和==)为例,其状态转移方程为:

f(n) = f(n-1) + f(n-2) (n >= 2)
其中,f(n)表示第n个斐波那契数;f(n-1)表示第n-1个斐波那契数;f(n-2)表示第n-2个斐波那契数。根据状态转移方程,我们可以通过求解第n-1个和第n-2个斐波那契数来求解第n个斐波那契数,从而计算出整个斐波那契数列。在这个例子中,状态转移方程描述了一个状态如何从前面的状态转移而来,即第n个斐波那契数等于前两个斐波那契数的和。
在实际应用中,状态转移方程是根据问题的具体特点而确定的,通常需要对问题进行抽象和分析,确定问题的状态和状态之间的关系,才能得到正确的状态转移方程。

背包问题

有一个容量为capacity的背包和n个物品,每个物品有一个重量和一个价值,要求选择一些物品放入背包中,使得背包的总重量不超过容量,且所选物品的总价值最大。
用动态规划算法求解:

public class KnapsackProblem {
    public static void main(String[] args) {
        int[] weights = {2, 2, 6, 5, 4};
        int[] values = {6, 3, 5, 4, 6};
        int capacity = 10;
        int maxValue = knapsack(weights, values, capacity);
        System.out.println("The maximum value is: " + maxValue);
    }
    public static int knapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[][] dp = new int[n + 1][capacity + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (weights[i - 1] <= j) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n][capacity];
    }
}

时间复杂度为O(n×capacity),空间复杂度为O(n×capacity)。

🌴解题

1.直接递归(超时)

  • code:
class Solution {
    public int coinChange(int[] coins, int amount) {
        int ans=mcoinChange(coins,amount);
        return ans==10000?-1:ans;
    }
    public static int mcoinChange(int[] coins, int amount) {
        if(amount==0)return 0;
        int res=10000;
        for (int i = 0; i < coins.length; i++) {
            if (amount >= coins[i]) {
                res = Math.min(mcoinChange(coins, amount - coins[i]) + 1, res);
            }
        }
        return res;
    }
}

2.动态规划

对于一个状态方程我们可以使用for循环进行展开:for (int j = 0; j < coins.length; j++)

  • code:
class Solution {
        public int coinChange(int[] coins, int amount) {
        if(amount==0)return 0;
        int res=1000000;
        int[] ans=new int[amount+1];
        ans[0]=0;//初始
        for (int i = 1; i <= amount; i++) {
            int temp=res;
            for (int j = 0; j < coins.length; j++) {
                if(i-coins[j]<0)
                    continue;
                temp= Math.min(ans[i-coins[j]]+1,temp);
            }
            ans[i]=temp;
           }

        return ans[amount]==res?-1:ans[amount];
    }
}

image.png


🌵Bug本是code常态,通过才是稀缺的意外!🌷

image.png

返回第一页。☝


☕物有本末,事有终始,知所先后。🍭

相关文章
|
24天前
|
缓存
力扣每日一题 6/14 动态规划+数组
力扣每日一题 6/14 动态规划+数组
17 1
|
1月前
|
存储 算法 数据可视化
深入解析力扣161题:相隔为 1 的编辑距离(逐字符比较与动态规划详解)
深入解析力扣161题:相隔为 1 的编辑距离(逐字符比较与动态规划详解)
|
24天前
|
算法 索引
力扣每日一题 6/28 动态规划/数组
力扣每日一题 6/28 动态规划/数组
19 0
|
24天前
|
存储
力扣每日一题 6/19 排序+动态规划
力扣每日一题 6/19 排序+动态规划
11 0
|
24天前
|
算法
力扣每日一题 6/16 字符串 + 随机一题 动态规划/数学
力扣每日一题 6/16 字符串 + 随机一题 动态规划/数学
14 0
|
26天前
|
机器人
【LeetCode】--- 动态规划 集训(二)
【LeetCode】--- 动态规划 集训(二)
17 0
|
26天前
【LeetCode】--- 动态规划 集训(一)
【LeetCode】--- 动态规划 集训(一)
11 0
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总(4)
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总
|
1月前
|
存储 算法
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总(1)
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总
|
1月前
|
存储 算法 数据挖掘
力扣174题动态规划:地下城游戏(含模拟面试)
力扣174题动态规划:地下城游戏(含模拟面试)