题目描述
题解一(动态规划)
思路
代码
classSolution{publicintcoinChange(int[]coins,intamount){// 给 dp 数组赋一个最大值，amount + 1 是一个不可能达到的上限值intmax=amount+1;int[]dp=newint[amount+1];// 初始化 dp 数组为最大值Arrays.fill(dp,max);// 凑成金额 0 不需要任何硬币dp[0]=0;// 遍历所有金额，计算每个金额所需的最少硬币数for(inti=1;i<=amount;i++){// 尝试使用每一种面值的硬币for(intj=0;j<coins.length;j++){if(coins[j]<=i){// 状态转移方程：当前金额的最少硬币数 = min(当前记录的最少硬币数, 减去当前硬币面值后的最少硬币数 + 1)dp[i]=Math.min(dp[i],dp[i-coins[j]]+1);}}}// 如果最终金额对应的硬币数仍然大于 amount，说明没有任何组合能凑出该金额，返回 -1returndp[amount]>amount?-1:dp[amount];}}复杂度分析
- 时间复杂度： O(S * n)，其中 S 是总金额 amount，n 是硬币数组的长度。我们需要计算 S 个状态，每个状态需要遍历 n 个面值
- 空间复杂度： O(S)。我们需要一个长度为 amount + 1 的一维数组来存储所有的状态值
题解二(记忆化搜索)
在使用纯递归时，我们会遇到大量重复计算的子问题（例如凑 amount=11 时计算了 amount=6，凑 amount=10 时可能又会计算一次 amount=6），这会导致超时。记忆化搜索的核心思想就是用一个备忘录（数组）把计算过的结果存起来，下次遇到相同的金额时直接查表返回
思路
代码
classSolution{// 备忘录数组int[]memo;publicintcoinChange(int[]coins,intamount){if(amount<1){return0;}// 初始化备忘录，长度为 amount + 1，默认值为 0 代表还未计算过memo=newint[amount+1];returndfs(coins,amount);}// 递归函数：返回凑出金额 remain 所需的最少硬币数量privateintdfs(int[]coins,intremain){// base case：金额小于 0，说明这个组合行不通if(remain<0){return-1;}// base case：金额等于 0，说明刚好凑完，需要 0 个硬币if(remain==0){return0;}// 如果备忘录中已经有记录（不为 0），直接返回，避免重复计算if(memo[remain]!=0){returnmemo[remain];}intmin=Integer.MAX_VALUE;// 遍历所有可以选择的硬币面值for(intcoin:coins){// 递归计算子问题：凑出 remain - coin 所需的最少硬币数intres=dfs(coins,remain-coin);// 如果子问题有解，且加上当前这枚硬币后总数更小，则更新最小值if(res>=0&&res<min){min=res+1;}}// 把计算结果存入备忘录。如果 min 还是 MAX_VALUE 说明没有任何硬币组合能凑出该金额，存入 -1memo[remain]=(min==Integer.MAX_VALUE)?-1:min;returnmemo[remain];}}复杂度分析
- 时间复杂度：O(S×n)O(S \times n)O(S×n)，其中SSS是总金额amountamountamount，nnn是面额数。由于使用了备忘录，规模为SSS的每个状态最多被计算 1 次，每次计算需要遍历nnn个硬币
- 空间复杂度：O(S)O(S)O(S)。递归树的深度最多为SSS（全用面值 1 的硬币），此时调用栈深为SSS；同时备忘录数组 memo 的长度也是S+1S + 1S+1。综合起来空间复杂度依然是O(S)O(S)O(S)
