leetcode-518-零钱兑换ii

[题目描述]

  1. //给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回
  2. // -1。
  3. //
  4. // 你可以认为每种硬币的数量是无限的。
  5. //
  6. //
  7. //
  8. // 示例 1：
  9. //
  10. //
  11. //输入：coins = [1, 2, 5], amount = 11
  12. //输出：3
  13. //解释：11 = 5 + 5 + 1
  14. //
  15. // 示例 2：
  16. //
  17. //
  18. //输入：coins = [2], amount = 3
  19. //输出：-1
  20. //
  21. // 示例 3：
  22. //
  23. //
  24. //输入：coins = [1], amount = 0
  25. //输出：0
  26. //
  27. //
  28. // 示例 4：
  29. //
  30. //
  31. //输入：coins = [1], amount = 1
  32. //输出：1
  33. //
  34. //
  35. // 示例 5：
  36. //
  37. //
  38. //输入：coins = [1], amount = 2
  39. //输出：2
  40. //
  41. //
  42. //
  43. //
  44. // 提示：
  45. //
  46. //
  47. // 1 <= coins.length <= 12
  48. // 1 <= coins[i] <= 231 - 1
  49. // 0 <= amount <= 104
  50. //
  51. // Related Topics 动态规划
  52. // 👍 1302 👎 0

[题目链接]

leetcode题目链接

[github地址]

代码链接

[相关题目链接]

leetcode-322-零钱兑换

本站链接

[思路介绍]

思路一：递归

  • 根据上一道零钱兑换可以求出最小解，同样的也可以求得方案总数当取完硬币后amount = 0 的时候也就可以代表此种方案满足题目要求res+=1
  • 也就是我们深度遍历所有可能性，对于所有amount=0的结果进行组合
  • 这种方案没有去重可以通过增加排序数进行去重处理（定义一个坐标，只允许往右取硬币，而不许往左取硬币）
  1. public int change(int amount, int[] coins) {
  2.             Arrays.sort(coins);
  3.             if (amount < 0) {
  4.                 return 0;
  5.             }
  6.             if (amount == 0) {
  7.                 return 1;
  8.             }
  9.             return dfs(coins, amount, 0,0);
  10.         }
  12.         public int dfs(int[] coins, int amount, int res, int index) {
  13.             if (amount == 0) {
  14.                 return res += 1;
  15.             }
  16.             if (amount < 0) {
  17.                 return res;
  18.             }
  19.             for (int i = index; i< coins.length; i++) {
  20.                 res = dfs(coins, amount - coins[i], res,i);
  21.             }
  22.             return res;
  23.         }

时间复杂度O(amount + nlgn ) n 表示为coins的长度

思路二：动态规划

  • 可以根据递归方程发现可变参数有两个，dp[i][j] 表示使用前i个硬币满足j价值的方案数
  • 首先定义边界情况当j = 0 的时候 dp[i][0] = 1当i = 0时 dp[0][j] = 0(初始化值)
  • 递推方程**dp[i][j] = dp[i-1][j] + sum(dp[i-1][j-(j/coins[i-1])coins[i-1]])
  1. public int change(int amount, int[] coins) {
  2.             int[][] dp = new int[coins.length + 1][amount + 1];
  3.             for (int i = 0; i <= coins.length; i++) {
  4.                 dp[i][0] = 1;
  5.             }
  6.             for (int i = 1; i <= coins.length; i++) {
  7.                 int val = coins[i - 1];
  8.                 for (int j = 0; j <= amount; j++) {
  9.                     dp[i][j] = dp[i - 1][j];
  10.                     for (int k = 1; k <= (j / val); k++) {
  11.                         dp[i][j] += dp[i - 1][j - k * val];
  12.                     }
  13.                 }
  15.             }
  16.             return dp[coins.length][amount];
  17.         }

**时间复杂度O(amount n + nlgn )n 表示为coins的长度

思路三：动态规划（一维优化）

  • 物品维度遍历了k次其实是为了保证所有元素都可以被遍历到我们可以取消j的遍历，而使用value作为遍历处理
  • 定义一个dp方程dp[i]表示达成容量为i的方案数方程意义表示为用前i个硬币
  • 分别满足j从0到amount-coins[i]的数量和也就是计算了所有j-coins[0-length-1]的值然后求和(也就是了减掉所有**valk)
  • 推导出如下方程dp[i] = sum(dp[i-(val->j)])初始化变量dp[0] = 1
  1. public int change(int amount, int[] coins) {
  2.             int[] dp = new int[amount + 1];
  3.             dp[0] = 1;
  4.             for (int i = 1; i <= coins.length; i++) {
  5.                 int val = coins[i - 1];
  6.                 for (int j = val; j <= amount; j++) {
  7.                     dp[j] += dp[j - val];
  8.                 }
  9.             }
  10.             return dp[amount];
  11.         }

**时间复杂度O(amount n)n表示为coins长度