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

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

算法专栏： 👉🏻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	...

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

动态规划算法思想

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

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

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

状态转移方程

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

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

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

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

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常态，通过才是稀缺的意外！🌷

返回第一页。☝

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

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