合江做网站/手机优化什么意思

322. 零钱兑换²

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

输入: coins = [2], amount = 3
输出: -1

解法：动态规划

• 思路：分解模型&&重复子问题（==>求分解出的每个金额最少需要多少硬币组合）
  • 状态数组：d[i][j]。 前 i 种硬币凑成金额 j 需要的最少硬币
  • 初始状态：
    • d[0][j]=Integer.MAX_VALUE。没有硬币那就组不出 j，但这里不能用-1因为如果取min，那么结果一定全是-1
    • d[i][0]=0。凑出金额0要0个硬币（由于数组默认初始值是0，所以不用再显式声明）
  • 状态方程：d[i] = min(d[i-1][j], d[i][j-c[i-1]] + 1)。构成金额j就两种方式
  • 最终状态：d[coins.len][amount]。len个硬币组成最终金额amout
• 复杂度：
  • Time：O(n * amount)
  • Space：O(n * amount)

public int coinChange(int[] coins, int amount) {// 状态数组int[][] d = new int[coins.length + 1][amount + 1];// 初始状态          for (int j = 0; j <= amount; j++) d[0][j] = Integer.MAX_VALUE;// 状态递推for (int i = 1; i <= coins.length; i++) {for (int j = 1; j <= amount; j++) {int useCurCoin = j >= coins[i - 1] ? d[i][j - coins[i - 1]] : Integer.MAX_VALUE;if (useCurCoin != Integer.MAX_VALUE) useCurCoin += 1;d[i][j] = Math.min(d[i - 1][j], useCurCoin);}}// 最终状态：d[coins.len][amount]return d[coins.length][amount] == Integer.MAX_VALUE ? -1 : d[coins.length][amount];}

518. 零钱兑换 II²

输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。

输入: amount = 10, coins = [10] 
输出: 1

解法一：分治（超时）

• 思路：分解模型（==>求分解出的每个金额可以有多少种组合方案）。递推公式，f(n) += f(n-coins[i]) i∈[0, coins.length)。

class Solution {public int change(int amount, int[] coins) {return changeConis(amount, 0, coins);}// start是防止重复答案（1,2,2）与 （2,2,1）// 比如在同一层，1 -> 2 // 2 -> 1private int changeConis(int money, int start, int[] coins) {if (money == 0) return 1;if (money < 0) return 0;int res = 0;for (int i = start; i < coins.length; i++) res += changeConis(money - coins[i], i, coins);return res;}
}

解法二：动态规划

• 思路：
  • 状态数组：d[i][j]。使用前 i 种面值的硬币（即c中0~i-1的元素），凑成金额 j 的组合数
  • 初始状态：
    • d[i][0]=1,。组成金额0只有一种方式
    • d[0][i]=0。没有硬币时组合方式为0（注：由于数组默认初始值是0，所以不用再显式声明）
  • 状态方程：d[i][j] = d[i - 1][j] + d[i][j - c[i-1]] (j - c[i-1] >= 0)。i 种面值的组合 = i-1的组合 + i 组成 j-c[i]，（例如，d[3][5] = d[2][5] + d[3][0]）
  • 最终状态：d[coins.len][amount]。
• 复杂度：
  • Time：O（n * amount)
  • Space：O（n * amount)

最优子结构 = 选择 || 淘汰。这里的逻辑树其实存在淘汰重复分支的思路，与爬楼梯问题一样

public int change(int amount, int[] coins) {// 1.状态方程int[][] d = new int[coins.length + 1][amount + 1];// 2.初始状态for(int i = 0; i <= coins.length; i++) d[i][0] = 1;// 3.状态递推      for (int i = 1; i <= coins.length; i++) {for (int j = 1; j <= amount; j++) {// 注：因为要保证j - coins[i-1] >= 0，所以先判断 d[i][j - c[i-1]]int userCurCoin = j >= coins[i - 1] ? d[i][j - coins[i - 1]] : 0;d[i][j] = d[i - 1][j] + userCurCoin;}}// 4.最终状态：d[coins.len][amount]return d[coins.length][amount];}