UVA 357 Let Me Count The Ways(全然背包)
题意:
有5种硬币: 1分 5分 10分 25分 和50分. 如今给你一个面值n, 问你有多少种方法能利用上述硬币组合出n分的金钱.
分析:
典型的全然背包问题.
本题的限制条件: 硬币钱数正好等于n
本题的目的条件: 求有多少种组合方法.
所以我们令dp[i][j]==x 表示用前i种硬币来构造j分金钱一共同拥有x种方法.
初始化: dp为全0. 但dp[0][0]=1.
状态转移: dp[i][j] = sum( dp[i-1][j] , dp[i][j-val[i]])
前者表示第i种硬币一个都不选, 后者表示至少选1个第i种硬币来用.
终于所求: dp[5][n].
程序实现用的滚动数组, 逆序递推. 所以dp仅仅有[j]这一维.
AC代码:
#include#include #include using namespace std;const int maxn = 30000+5;int n=5;int val[]={1,5,10,25,50};long long dp[maxn];int main(){ //初始化 memset(dp,0,sizeof(dp)); dp[0]=1; //递推 for(int i=0;i