题解 P1474 【货币系统 Money Systems】

· · 题解

看没有写C++短代码题解的就来一发~

这题就是一个完全背包问题

dp方程 x(i)=sum(x(i-h(j)) 边界x(0)=1

其中x(i)代表凑成i元有x(i)种方法，h(j)代表第j个货币的面值

#include<bits/stdc++.h>
long long v,n,h[30],dp[10005]={1};
int main(){
    std::cin>>v>>n;
    for(int i=0;i<v;i++) std::cin>>h[i];
    for(int i=0;i<v;i++)for(int j=h[i];j<=n;j++) dp[j]+=dp[j-h[i]];
    std::cout<<dp[n];
    return 0;
}