道阻且长行则将至。

---

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

算法专栏 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种可能取值125。
  假如我们设置一个函数来求解最少需要用多少枚硬币凑出xf(x)。
  那么当c_k=1f(11)=f(10)+1——就是当最后一枚硬币是1那我们就要进一步求如何最小的凑出10
  那么当c_k=2f(11)=f(9) + 1——就是当最后一枚硬币是2那我们就要进一步求如何最小的凑出9
  那么当c_k=5f(11)=f(6) + 1——就是当最后一枚硬币是5那我们就要进一步求如何最小的凑出6
  这时候我们发现上面就是f(11)=min{f(10)+1f(9) + 1f(6) + 1}后面也是类似的过程于是我们可以写出一个递归实现的方法跳转到递归实现。
• 但是递归实现仍然时间复杂度太高我们继续上面的推一下就会发现里面存在大量重复计算例如在计算f(10)又会出现f(9)…
  还是对于f(11)=min{f(10)+1f(9) + 1f(6) + 1}我们可以写为f(x)=min{f(x-1)+1f(x-2) + 1f(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☝☝☝☝☝☝