问题描述

coins 是面值数组，其中的值都是正数且没有重复。再给定一个正数 aim。每个值都认为是一种面值，且认为张数是无限的。返回组成 aim 的方法数。

例如: arr = {1,2}，aim = 4 ，方法有: 1+1+1+1、1+1+2、2+2，一共 3 种方法，所以返回 3 。

暴力递归

思路同动态规划-完全背包中的补充部分，不再赘述，直接给出代码：

int process(const vector<int> &coins, int rest, int index)
{
    if(rest == 0)//必须置于下一个if之前
        return 1;
    if(index >= coins.size())
        return 0;
    int ret = 0;
    for(int i = 0; i * coins[index] <= rest; i++)
    {
        ret += process(coins, rest - i * coins[index], index + 1);
    }
    return ret;
}
int coins(const vector<int> &coins, int aim)
{
    return process(coins, aim, 0);
}

动态规划

int help(int size, int rest, int index, 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<vector<int>> dp(aim + 1, vector<int>(coins.size(), 0));
    for(int rest = 0; rest <= aim; rest++)
    {
        for(int index = coins.size() - 1; index >= 0; index--)
        {
            int ret = 0;
            for(int i = 0; i * coins[index] <= rest; i++)
            {
                ret += help(coins.size(), rest - i * coins[index], index + 1, dp);
            }
            dp[rest][index] = ret;
        }
    }
    return dp[aim][0];
}

斜率优化

仔细分析一下依赖关系，假设 rest=5 、index=3 ，且 coins[3]=2 ，即下面的紫色方格：

根据动态规划的第 16~21 行代码可知紫色格子是右侧三个棕色格子的总和。

再将目光转到红色五角星，同样可以推出它依赖的是右边的四颗黄色五角星。我们惊人地发现棕色格子和上面的三个黄色五角星完全重合！

所以红色五角星的依赖可以转化为紫色格子和右侧黄色五角星（[7][4]）的和，这样就可以省去对其他黄色五角星的枚举（for循环）。代码如下：

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

需要注意的是，第 5 行增加了 rest<0 的判断。因为之前有 for 循环的终止条件 i * coins[index] <= rest 把控，所以后续递归中不会出现 rest<0 的情况，而现在我们删去了 for 循环，所以必须自己处理 rest<0 的情况。

总结

• 本题属于 完全背包问题 ，每一个项的数量可以取无数次。
• 有的题目斜率优化很难看出来，一定要动手画图并举出具体的例子。
• 如果暴力递归中没有 for 循环，那么记忆化搜索和动态规划的复杂度一样；如果有 for 循环，则应该尝试改为动态规划表，然后通过观察依赖关系看是否能够进一步优化。因为在递归无法通过剪枝来完成类似斜率优化这种操作，这只能通过修改表的依赖来完成！而且只有画出表格才方便观察依赖关系。