LeetCode 518. 零钱兑换 II 【c++/java详细题解】

x33g5p2x  于2021-09-20 转载在 C/C++  
字(2.3k)|赞(0)|评价(0)|浏览(288)

1、题目

给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例 1:

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

示例 2:

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

示例 3:

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

提示:

  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • coins 中的所有值 互不相同
  • 0 <= amount <= 5000

2、思路

(动态规划,完全背包)

二维分析

状态表示:f[i][j] 表示从前i种硬币中选,且总金额恰好为j的所有选法集合的方案数。

那么f[n][amount]就表示表示从前n种硬币中选,且总金额恰好为amount的所有选法集合的方案数,即为答案。

集合划分:

按照第i种硬币可以选 0个,1个,2个,3个,,,,k个划分集合 f[i][j]。其中k/*coin[i] <= j,也就是说在背包能装下的情况下,枚举第i种硬币可以选择几个。

  • i种硬币选 0个,f[i][j] = f[i-1][j]
  • i种硬币选 1个,f[i][j] = f[i-1][j - coins[i]]
  • i种硬币选 k个,f[i][j] = f[i-1][j - k/*coins[i]]

状态计算:

f[i][j] = f[i-1][j]+f[i-1][j-coins[i]]+f[i-1][j-2/*coins[i]],,,,,,+f[i-1][j-k/*coins[i]]
初始化条件:

  • f[0][0] = 1,使用0种硬币币,凑0元钱,也是一种方案。

**时间复杂度分析:**O ( a m o u n t 2 ∗ n ) O(amount^2/*n)O(amount2∗n),其中 a m o u n t amountamount是总金额,n nn是数组 c o i n s coinscoins的长度。

3、二维c++代码

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        vector<vector<int>>f(n + 1, vector<int>(amount + 1 , 0));
        f[0][0] = 1;  // 使用0种货币,凑0元钱,也是一种方案
        for(int i = 1; i <= n; i++)
        {
            int v =coins[i - 1];
            for(int j = 0; j <= amount; j++)
                 for(int k = 0; k*v <= j; k++)
                   f[i][j] += f[i-1][j-k*v];    //状态计算方程
        }
        return f[n][amount];        
    }
};

4、二维java代码

class Solution {
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[][] f = new int[n + 1][amount + 1];
        f[0][0] = 1;   // 使用0种货币,凑0元钱,也是一种方案
        for (int i = 1; i <= n; i++) {
            int v = coins[i - 1];
            for (int j = 0; j <= amount; j++) 
                for (int k = 0; k * v <= j; k++) 
                    f[i][j] += f[i - 1][j - k * v];  //状态计算方程
        }
        return f[n][amount];
    }
}

5、一维优化

二维完全背包求解方案时间复杂度较高,考虑一维优化。

v代表第i种硬币的面值

f[i][j] = f[i-1][j] + f[i-1][j-v]+f[i-1][j-2v]+,,,,,+f[i-1][j-kv])

f[i][j-v] = f[i-1,[j-v]+f[i-1][j-2v]+,,,,,+f[i-1][j-kv])

因此:

f[i][j] = f[i-1][j]+f[i][j-v])

图示:

去掉物品种类维度,状态计算方程为:f[j] = f[j] + f[j-v]

**时间复杂度分析:**O ( a m o u n t ∗ n ) O(amount/*n)O(amount∗n) ,其中 a m o u n t amountamount是总金额,n nn是数组 c o i n s coinscoins的长度。

6、一维c++代码

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int>f(amount + 1);
        f[0] = 1; //f[0][0] = 1;
        for(int i = 1; i <= coins.size(); i++)
        {
            int v =coins[i - 1];
            for(int j = v; j <= amount; j++)
                f[j] += f[j - v];
        }
        return f[amount];        
        
    }
};

7、一维java代码

class Solution {
    public int change(int amount, int[] coins) {
        int[] f = new int[amount + 1];
        f[0] = 1; //f[0][0] = 1;
        for(int i = 1; i <= coins.length; i++)
        {
            int v =coins[i - 1];
            for(int j = v; j <= amount; j++)
                f[j] += f[j - v];
        }
        return f[amount];       
    }
}

原题链接:518. 零钱兑换 II

相关文章