leetcode-518-零钱兑换ii

[题目描述]

//给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回
// -1。
//
// 你可以认为每种硬币的数量是无限的。
//
//
//
// 示例 1：
//
//
//输入：coins = [1, 2, 5], amount = 11
//输出：3
//解释：11 = 5 + 5 + 1
//
// 示例 2：
//
//
//输入：coins = [2], amount = 3
//输出：-1
//
// 示例 3：
//
//
//输入：coins = [1], amount = 0
//输出：0
//
//
// 示例 4：
//
//
//输入：coins = [1], amount = 1
//输出：1
//
//
// 示例 5：
//
//
//输入：coins = [1], amount = 2
//输出：2
//
//
//
//
// 提示：
//
//
// 1 <= coins.length <= 12
// 1 <= coins[i] <= 231 - 1
// 0 <= amount <= 104
//
// Related Topics 动态规划
// ? 1302 ? 0
复制代码

[题目链接]

leetcode题目链接

[github地址]

代码链接

[相关题目链接]

leetcode-322-零钱兑换

本站链接

[思路介绍]

思路一：递归

根据上一道零钱兑换可以求出最小解，同样的也可以求得方案总数当取完硬币后amount = 0 的时候也就可以代表此种方案满足题目要求res+=1
也就是我们深度遍历所有可能性，对于所有amount=0的结果进行组合
这种方案没有去重可以通过增加排序数进行去重处理（定义一个坐标，只允许往右取硬币，而不许往左取硬币）

public int change(int amount, int[] coins) {
            Arrays.sort(coins);
            if (amount < 0) {
                return 0;
            }
            if (amount == 0) {
                return 1;
            }
            return dfs(coins, amount, 0,0);
        }

        public int dfs(int[] coins, int amount, int res, int index) {
            if (amount == 0) {
                return res += 1;
            }
            if (amount < 0) {
                return res;
            }
            for (int i = index; i< coins.length; i++) {
                res = dfs(coins, amount - coins[i], res,i);
            }
            return res;
        }
复制代码

时间复杂度O(amount^n^ + 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]])*

public int change(int amount, int[] coins) {
            int[][] dp = new int[coins.length + 1][amount + 1];
            for (int i = 0; i <= coins.length; i++) {
                dp[i][0] = 1;
            }
            for (int i = 1; i <= coins.length; i++) {
                int val = coins[i - 1];
                for (int j = 0; j <= amount; j++) {
                    dp[i][j] = dp[i - 1][j];
                    for (int k = 1; k <= (j / val); k++) {
                        dp[i][j] += dp[i - 1][j - k * val];
                    }
                }

            }
            return dp[coins.length][amount];
        }
复制代码

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

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

物品维度遍历了k次其实是为了保证所有元素都可以被遍历到我们可以取消j的遍历，而使用value作为遍历处理
定义一个dp方程dp[i]表示达成容量为i的方案数方程意义表示为用前i个硬币
分别满足j从0到amount-coins[i]的数量和也就是计算了所有j-coins[0-length-1]的值然后求和(也就是了减掉所有val*k)
推导出如下方程dp[i] = sum(dp[i-(val->j)])初始化变量dp[0] = 1

public int change(int amount, int[] coins) {
            int[] dp = new int[amount + 1];
            dp[0] = 1;
            for (int i = 1; i <= coins.length; i++) {
                int val = coins[i - 1];
                for (int j = val; j <= amount; j++) {
                    dp[j] += dp[j - val];
                }
            }
            return dp[amount];
        }
复制代码