问题描述

coins 是货币数组，其中的值都是正数。再给定一个正数 aim。每个值都认为是一张货币，即便是值相同的货币也认为每张都是不同的，返回组成 aim 的方法数。

例如: coins = {1,1,1}，aim = 2 ，则第 0 个和第 1 个能组成 2 ，第 1 个和第 2 个能组成 2 ，第 0 个和第 2 个能组成 2 ，一共就3种方法，所以返回 3 。

暴力递归

仍然是常见的从左往右、要或不要模型。直接给出代码：

int process(const vector<int> &coins, int rest, int index)
{
    if(rest == 0)//必须放在下一个if之前,因为可能刚好拿走最后一个硬币时,rest变为0
        return 1;
    if(index >= coins.size() || rest < 0)
        return 0;
    int ret1 = process(coins, rest, index + 1);//不要
    int ret2 = process(coins, rest - coins[index], index + 1);//要
    return ret1 + ret2;
}
int coins(const vector<int> &coins, int aim)
{
    return process(coins, aim, 0);
}

动态规划

int help(const vector<int> &coins, const vector<vector<int>> &dp, int rest, int index)
{
    if(rest == 0)
        return 1;
    if(index >= coins.size() || rest < 0)
        return 0;
    return dp[rest][index];
}
int coins(const vector<int> &coins, int aim)
{
    vector<vector<int>> dp(aim + 1, vector<int>(coins.size(), 0));
    //依赖右边和右上格子,因此打表顺序为从上到下,从右往左
    for(int r = 0; r <= aim; r++)
    {
        for(int i = coins.size() - 1; i >= 0; i--)
        {
            int ret1 = help(coins, dp, r, i + 1);
            int ret2 = help(coins, dp, r - coins[i], i + 1);
            dp[r][i] = ret1 + ret2;
        }
    }
    return dp[aim][0];
}

总结

本题属于 01 背包问题，仍然可以按照之前总结的从左到右、要或不要模型解决。作为对比，请继续浏览动态规划-硬币系列2、动态规划-硬币系列3、动态规划-硬币系列4。