algo-aha

不同找零方式数

设f(m,n)表示前m种硬币凑n分钱的方式数，

f(m, n) = f(m-1, n) /*不取第m种硬币*/ + f(m, n-v[m]) /*取第m种硬币*/，初始f(0,0)=1、其他为0（无效）

用完全背包的一维数组写法，对某种硬币面值，正序遍历各个“容量”（要凑的钱数），f(n) = f(n) + f(n-v[m])

为什么这题不能像求走台阶的方式数那样 f(n) = f(n-v1) + f(n-v2) + ... + f(n-vm) 呢？因为比如走4级台阶，先走1步再走3步，和先走3步再走1步是不同的。而找4分零钱，先找1分再找3分，和先找3分再找1分是相同的。比如要从{1, 3}两种面值硬币中找4分钱，用走台阶法 f(0)=1、f(1)=1、f(2)=f(1)=1、f(3)=f(2)+f(0)=2、f(4)=f(3)+f(1)=3就是错的，它重复计算了{3, 1}和{1, 3}两种情况。走台阶法对应着"排列"，而背包问题对应着"组合"。

最少使用硬币数

• https://leetcode.com/problems/coin-change/

设f(m,n)表示前m种硬币凑n分钱的最少使用硬币数，

f(m, n) = min{ f(m-1, n), f(m, n-v[m])+1 }，初始f(0,0)=0、其他为∞（无效）

用完全背包问题的一维数组写法，对某种硬币面值，正序遍历各个“容量”（要凑的钱数），f(n) = min{ f(n), f(n-v[m])+1 }

int coinChange(vector<int>& coins, int amount) {
    // 完全背包问题：选最少的硬币数使面值总和为amount
    const int THE_MAX = amount + 1;
    vector<int> dp(amount + 1, THE_MAX);
    dp[0] = 0;
    for (int c : coins) {
        for (int v = c; v <= amount; v++) { // 正序遍历各容量
            dp[v] = min(dp[v], dp[v-c] + 1);
        }
    }
    return (dp[amount] != THE_MAX) ? dp[amount] : -1;
}