leetcode-518-零钱兑换II

零钱兑换 II

题面

leetcode题目

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

example

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

• \(5=5\)
• \(5=2+2+1\)
• \(5=2+1+1+1\)
• \(5=1+1+1+1+1\)

数据范围

• \(0 \leq amount \leq 5000\)
• \(1 \leq coin \leq 5000\)
• 硬币种类不超过 \(500\) 种
• 结果符合 \(32\) 位符号整数

题解

总体思路

很简单的dp了，考虑\(dp[i][j]\)表示选择完第\(i\)种硬币后能凑出目标金额\(j\)的组合数，那么有: \[ dp[i][j] = \sum_{k=0}^{\frac{j}{coins[i]}} dp[i-1][j - k*coins[i]] \qquad j-k*coins[i] \geq 0 \tag{1}\] \((1)\)式可以这样理解，在决定第\(i\)种硬币时，可以考虑取\(k\)枚这种硬币，\(k\)的取值范围为\(0 \leq k \leq \frac{target}{coins[i]}\)，其中\(target\)为目标凑出的金额数，并且需要满足\(j-k*coins[i] \geq 0\)。
这里可以用滚动数组优化一下空间。

代码

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define _DEBUG
#define LL long long

class Solution
{
public:
    int change(int amount, vector<int> &coins)
    {
        int len = coins.size();
        int dpPre[amount + 1];
        int dp[amount + 1];
        memset(dpPre, 0, sizeof(dpPre));
        memset(dp, 0, sizeof(dp));
        dpPre[0] = 1;
        for (int i = 0; i < len; i++)
        {
            int coin = coins[i];
            int max = amount / coin;
            for (int j = 0; j \leq amount; j++)
            {
                int div = j / coin;
                for (int k = 0; k \leq div && j - coin * k >= 0; k++)
                {
                    dp[j] += dpPre[j - coin * k];
                }
#ifdef _DEBUG
                if (dp[j] > 0)
                {
                    cout << "i: " << i << " j: " << j << " dp[i][j]: " << dp[j] << endl;
                }
#endif
            }
            memcpy(dpPre, dp, sizeof(dp));
            memset(dp, 0, sizeof(dp));
        }
        return dpPre[amount];
    }
};

// for test
int main()
{
    Solution s;
    vector<int> t1{1, 2, 5};
    cout << s.change(5, t1) << endl;

    return 0;
}