「CodeNote」完全背包计数

题意

给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)

输入: 0 <= n (总金额) <= 1000000

经典背包方案数问题

硬币数量不限,是完全背包问题,但是这个题是方案数,如果直接按照背包问题的思路进行计算,会导致重复的情况

比如dp[1]=1 dp[5]=2是显然的,如果考虑到6个硬币是由1和5转移的,则有dp[6]=dp[6-5]+dp[6-1]=3,但是实际上dp[6]=2,是因为产生了重复的计算.

这个问题如果想要计算后去重实际上比较困难(因为状态太多了),所以只能从状态转移的时候去重.

去重思路如下:

我们从完全背包中获取灵感f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}
令dp[i][j]表示用前 i 种硬币凑出j分的方法数
dp[i][j]=dp[i-1][j]+dp[i][j-coin[i]]这两种状态是不会重复的(可借助完全背包来理解)
- 因为前者是不用第i种硬币的方案数
- 后者是使用至少一个i种硬币凑够j分的方法数,加起来就是使用前i种硬币凑够j分的总方法数.
将第一维滚动掉,因此得到完整答案

// 将dp数组清空
dp[0]=1;
for(int j=0;j<4;++j){
    for(int i=coin[j];i<=n;++i){
        dp[i]=(dp[i]+dp[i-coin[j]])%1000000007;
    }
}