问题描述

coins 是货币数组，其中的值都是正数，每个值都认为是一张货币（而非面值），且值相同的货币没有任何不同，再给定一个正数 aim。返回组成 aim 的方法数。

例 1: coins = {1,2,1,1,2,1,2}，aim=4

方法：1+1+1+1、1+1+2、 2+2 ，一共 3 种方法， 所以返回 3 。

例 2：coins = {1,1,2,2}，aim=2

方法：1+1、2 ，一共 2 种方法，所以返回 2 。

暴力递归

仔细揣摩题目，“每个值都认为是一张货币（而非面值），认为值相同的货币没有任何不同”。实际上本题可以翻译为：coins 是 info 数组，info 结构体中包含 value 和 count 两个整形，分别指该货币的面值和数量 。比如上面的例 1 中，面值为 1 的货币有 4 张，面值为 2 的货币有 3 张，统计好各货币的 info 然后存入数组即可。

经过这样的转换，题意就清楚多了。本题相比于动态规划-硬币系列2就仅仅多了货币个数的限制，其他几乎完全相同。

struct info
{
    int value;
    int count;
    explicit info(int _value = 0, int _count = 0):value(_value), count(_count){};
};
int process(const vector<info> &coin, int rest, int index)
{
    if(rest == 0)//必须置前
        return 1;
    if(index >= coin.size())
        return 0;
    int ret = 0;
    for(int i = 0; i * coin[index].value <= rest && i <= coin[index].count; i++)//注意此处多了一个条件
    {
        ret += process(coin, rest - i * coin[index].value, index + 1);
    }
    return ret;
}
int coins(const vector<int> &coins, int aim)
{
    vector<info> coin;
    unordered_map<int, int> map;
    for(int c : coins)//统计面值及其出现次数
    {
        if(map.find(c) == map.end())
        {
            coin.emplace_back(c, 1);
            map.emplace(c, coin.size() - 1);
        }
        else
            coin[map[c]].count++;
    }
    return process(coin, aim, 0);
}

本题主逻辑代码只比动态规划-硬币系列2多了第 14 行的一个条件：i <= coin[index].count 。

动态规划

int help(int rest, int index, int size, const vector<vector<int>> &dp)
{
    if(rest == 0)//必须置前
        return 1;
    if(index >= size)
        return 0;
    return dp[rest][index];
}
int coins(const vector<int> &coins, int aim)
{
    vector<info> coin;
    unordered_map<int, int> map;
    vector<vector<int>> dp(aim + 1, vector<int>(coins.size(), 0));
    for(int c : coins)//统计面值及其出现次数
    {
        if(map.find(c) == map.end())
        {
            coin.emplace_back(c, 1);
            map.emplace(c, coin.size() - 1);
        }
        else
            coin[map[c]].count++;
    }

    for(int rest = 0; rest <= aim; rest++)
    {
        for(int index = coin.size() - 1; index >= 0; index--)
        {
            int ret = 0;
            for(int i = 0; i * coin[index].value <= rest && i <= coin[index].count; i++)
                ret += help(rest - i * coin[index].value, index + 1, coin.size(), dp);
            dp[rest][index] = ret;
        }
    }
    return dp[aim][0];
}

斜率优化

对比动态规划-硬币系列2的斜率优化，此处多了一个限制条件。仍假设 rest=5 、index=3 ，且 coin[3].value=1 、coin[3].count=2 ，则依赖关系如下图：

推出依赖关系式：红色五角星 = 紧邻右边的黄色五角星 + 紫色方格 - 最上方的棕色方格

最后得到以下代码：

int help(int rest, int index, int size, const vector<vector<int>> &dp)  
{  
    if(rest == 0)//必须置前  
        return 1;  
    if(rest < 0 || index >= size)  
        return 0;  
    return dp[rest][index];  
}
int coins(const vector<int> &coins, int aim)  
{  
//......
    for(int rest = 0; rest <= aim; rest++)  
    {  
        for(int index = coin.size() - 1; index >= 0; index--)  
        {  
            dp[rest][index] = help(rest, index + 1, coin.size(), dp)  
                            + help(rest - coin[index].value, index, coin.size(), dp)  
                            - help(rest - (coin[index].count + 1) * coin[index].value, index + 1, coin.size(), dp);  
        }  
    }  
    return dp[aim][0];  
}

总结

• 本题属于多重背包问题。
• 斜率优化务必画图仔细分析，重叠和非重叠部分尤其需要注意。