P2834 纸币问题 3 题解

· · 题解

前言

第一眼看见很像数楼梯呀，所以运用了这种思路去思考这道题，当然不是用斐波拉契。

思路简介

首先，很明显能观察到对于每一张纸币 i，它的方案数就是所有比它面额小 k 的纸币的方案数之和。

于是我联想到数楼梯的递推法，所以同样是用的递推，每输进来一个数，就加上 a_{j-k} 的组合方案数得到 a_j 新的组合方案数。

代码

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int main(){
    int a[1001],k;
    a[0]=1;
    int n,w;
    cin>>n>>w;
    for(int i=1;i<=n;i++){
        cin>>k;
        for(int j=k;j<=w;j++){
            a[j]=(a[j]+a[j-k])%mod;
        }
    }
    cout<<a[w];
}

温馨提示

与数楼梯一样的一点是 a_0 要赋值为 1，因为组成 0 元的方案数是 1 种。