问题描述

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

返回组成 aim 的最少货币数。

暴力递归

本题求的是最少货币数，而本系列的前几题都是求的方法数，这两者的区别已经在动态规划-完全背包的补充内容中说明过，不再赘述。

int process(const vector<int> &coins, int rest, int index)
{
    if(rest == 0)//必须置前
        return 0;
    if(index >= coins.size())
        return INT32_MAX;
    int min = INT32_MAX;
    for(int i = 0; i * coins[index] <= rest; i++)
    {
        int ret = process(coins, rest - i * coins[index], index + 1);
        if(ret != INT32_MAX)//防止INT32_MAX+1溢出
            min = min < ret + i ? min : ret + i;//别忘了加上本次使用的货币数量i
    }
    return min;
}
int coins(const vector<int> &coins, int aim)
{
    return process(coins, aim, 0);
}

动态规划

int help(int rest, int index, int size, const vector<vector<int>> &dp)
{
    if(rest == 0)//必须置前
        return 0;
    if(index >= size)
        return INT32_MAX;
    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 min = INT32_MAX;
            for(int i = 0; i * coins[index] <= rest; i++)
            {
                int ret = help(rest - i * coins[index], index + 1, coins.size(), dp);
                if(ret != INT32_MAX)
                    min = min < ret + i ? min : ret + i;
            }
            dp[rest][index] = min;
        }
    }
    return dp[aim][0];
}

斜率优化

本题的斜率优化和动态规划-硬币系列2完全类似，只是本题是求最小值，而系列2是求和。还是拿之前的图举例：

紫色方格 = 三个棕色方格中最小的

别忘了上面第 21 行代码 min = min < ret + i ? min : ret + i ， 所以棕色方格的值 ret 还需要加上 i ，即图中棕色方块右上角的数字。

所以红色五角星 = min(紫色方格 + 1, 右边紧邻的黄色五角星)

为什么要 +1 ？仔细看图思考。

int help(int rest, int index, int size, const vector<vector<int>> &dp)
{
    if(rest == 0)//必须置前
        return 0;
    if(rest < 0 || index >= size)
        return INT32_MAX;
    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 val = help(rest - coins[index], index, coins.size(), dp);
            dp[rest][index] = std::min(
                    val == INT32_MAX ? INT32_MAX : val + 1,//防止+1溢出
                    help(rest, index + 1, coins.size(), dp)
                    );
        }
    }
    return dp[aim][0];
}

总结

• 本题和动态规划-硬币系列2一样，都属于 完全背包 问题。
• 本题的斜率优化更加隐蔽，还需要加 1 进行转换，要求更加细心的观察。