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

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

---

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

算法专栏： 👉🏻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];}
}

---

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

返回第一页。☝

---

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

🍎☝☝☝☝☝我的CSDN☝☝☝☝☝☝🍓