518_coins_changeII_找零钱II

问题描述

链接：https://leetcode.com/problems/coin-change-ii/

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.'
Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.
You may assume that you have an infinite number of each kind of coin.

The answer is guaranteed to fit into a signed 32-bit integer.

解释: 给定一些零钱\(coins\)， 用一个整数amount表示金钱，将amount兑换成零钱，问总共有多少种方法？如果没有一种方法，则返回0

案例解析：

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
解释： amount = 5, 用数组中的零钱有4种兑换方案

基本思想

注意：零钱数量是无限的
这个是一个二维动态规划问题，假设coins的大小是n, 用m替换amount 则构建二维数组 dp, dp的大小为 n * (m+1)
\(dp[i][j]\) 表示 用coins[0~i-1]构成 amount=j的组合数目，则\(dp[i][j]\)更新公式如下：
\(dp[i][j]\) = \(dp[i-1][j]\) + \(dp[i][j-coins[i]]\)

• \(dp[i-1][j]\) 表示不使用\(coins[i]\)构成amount=j 即不实用 coins[j]构成j的组合数目
• \(dp[i][j-coin[i]]\) 表示 使用 \(coins[i]\) 构成 amount=j的数量

注意：这个问题和0-1背包问题比较像

动态规划

动态规划三种思路：

• 一维
• 一维不行上二维
• 如果实在没有思路，就从简单入手，凭直觉。比如 股票买卖问题

代码

C++

    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        if (n<=0) return 0;
        if (amount<=0) return 1;
        vector<vector<int>> dp(n, vector<int>(amount+1,0));
        sort(coins.begin(), coins.end()); // coins不能有重复

        for(int i=1;i<=amount;++i) {
            if (i%coins[0] == 0) {
                dp[0][i] = 1;
            }
        }
        for(int i=0;i<coins.size();++i) {
            dp[i][0] = 1; // 初始化存疑
        }
        for(int i=1;i<coins.size();++i) {
            for(int j=1;j<=amount;++j) {
                if (j<coins[i]) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]];
                }
            }
        }
        return dp[n-1][amount];
    }

python

    def change(self, amount: int, coins: List[int]) -> int:
        n = len(coins)
        if amount<=0: return 1
        if n<=0: return 0
        dp = [[0 for j in range(0,amount+1)] for i in range(n)]
        for ele in range(0, amount+1):
            if ele % coins[0] == 0:
                dp[0][ele] = 1;
        for index in range(0, n): # amount=0的时候，初始化为1 
            dp[index][0] = 1
        for i in range(1,n):
            for j in range(1, amount+1):
                if j < coins[i]: 
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]]
        return dp[n-1][amount]