一、题意

给定金额n，有50, 25, 10, 5, 1这五种面值的钱，问共有多少种不同的找法。

二、解析

看到这道题，第一反应是用DAG的记忆化搜索法求解，即每个金额V指向V-coins[i]。但这样会出现一个问题，就是重复计数的问题。比如16块钱，10->5->1的找法和1->5->10的找***被当作不同的找法，这是不对的。如果用递推法中的填表法也是一样，无法避免重复计算的问题。

这个时候就得使用递推法中的“刷表法”了。

即用每一种面值的纸币coins[i]去分别“更新”每一种金额j的找法数量dp[j]。
比如，当只有10这个面值时，找10块钱金额只有 10 一种找法，当新增一种面值5时，找法数量就在原来的基础上新增了包含5的这一部分，即5->5这种找法。通过这样刷表，就不出现重复了。

三、代码

#include <iostream>
using namespace std;
const int N = 10000;
const int coins[5] = {50, 25, 10, 5, 1};
int dp[N];

int main() {
    fill(dp, dp + N, 0);
    dp[0] = 1;
    for(int i = 0; i < 5; i ++) {  // 每次增加一种面值进行刷表法
        for(int j = coins[i]; j < N; j ++) {  // 每一种金额利用新面值都会新增一些凑法，无需考虑数量
            dp[j] += dp[j - coins[i]];
        }
    }
    int num;
    while(cin >> num) cout << dp[num] << endl;
}

四、归纳

  • 填表法：对于每一种状态i，更新dp[i]
  • 刷表法：对于每一种状态i，更新dp[i]
  • 当填表法难以实现时，想想看能不能用刷表法
  • 计数类的问题时，注意会不会出现重复问题
  • 有时候可以在刷表/填报完成后，再进行输入和输出，即预先算好所有答案值，以加快速度