面试题 08.11. 硬币

设F(i, v)为前i种面值硬币构成面额为v的方案数。

(题中i为4，且面额为[1, 5, 10, 25])

将第i个面额记为c_i

则转移方程 \[ F(i, v) = F(i - 1, v - 0 * c_i) + F(i - 1, v - 1 * c_i) + F(i - 1, v - 2 * c_i) + ... + F(i - 1, v - v/c_i * c_i) \]

这是一个纵轴为采用的硬币种类，横轴为面额，内部值为方案数的表格

以上的原始版本的代码实现


class Solution {
public:
    int waysToChange(int n) {
        int coins[4]{1, 5, 10, 25};
        vector> dp(5, vector(n + 1, 0));
        dp[0][0] = 1;
        for(int i = 1; i <= 4; ++i)
        {
            dp[i][0] = 1;
            auto coin = coins[i - 1];
            for(int j = 1; j <= n; ++j)
            {
                dp[i][j] = dp[i - 1][j];
                for(int k = 1; k <= j / coin; ++k)
                {
                    dp[i][j] += dp[i - 1][j - k * coin];
                    dp[i][j] %= 1000000007;
                }
            }
        }
        return dp.back().back();
    }
};

但是超时了

进行对时间的优化 \[ F(i, v) = F(i - 1, v - 0 * c_i) + F(i - 1, v - 1 * c_i) + F(i - 1, v - 2 * c_i) + ... + F(i - 1, v - v/c_i * c_i) \] 图中标红的公式与 \[ F(i, v - c_i) = F(i - 1, v - 1 * c_i) + F(i - 1, v - 2 * c_i) + ... + F(i - 1, v - v/c_i * c_i) \] 进行比较，发现相同，所以 \[ F(i, v) = F(i - 1, v - 0 * c_i) + F(i, v - c_i) \] 于是就可以减少一层循环

以上的优化时间版本的代码实现


class Solution {
public:
    int waysToChange(int n) {
        int coins[4]{1, 5, 10, 25};
        vector> dp(5, vector(n + 1, 0));
        dp[0][0] = 1;
        for(int i = 1; i <= 4; ++i)
        {
            dp[i][0] = 1;
            auto coin = coins[i - 1];
            for(int j = 1; j <= n; ++j)
            {
                dp[i][j] = dp[i - 1][j];
                if(j >= coin)
                    dp[i][j] += dp[i][j - coin];
                dp[i][j] %= 1000000007;
            }
        }
        return dp.back().back();
    }
};

对空间优化

发现每次循环仅仅使用到了上一层的数据，因此可以将空间使用从二维减少到一维，就用常规的方式即可

最终版本的代码

T(n) : O(n)

S(n) : O(n)

class Solution {
public:
    int waysToChange(int n) {
        int coins[4]{1, 5, 10, 25};
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        for(int i = 1; i <= 4; ++i)
        {
            auto coin = coins[i - 1];
            for(int j = coin; j <= n; ++j)
            {
                dp[j] = dp[j] + dp[j - coin];
                dp[j] %= 1000000007;
            }
        }
        return dp.back();
    }
};

还有数学方法，抄累了