题意描述：
有几种面额固定的硬币，每种面额的硬币都有无数张。给你一定的金额，问总共有多少种找零方案。
完全背包问题，动态方程为：f[j] += f[j - mny[i]];
myi[i]表示第i种硬币的面值，f[j]表示数额为j的找零方案。
表示对完全背包的动态方程不甚理解，希望大神不惜指点。。
以下是本题代码：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 350
#define LENM 20
int main()
{
int i, j;
int f[LEN];
int mny[LENM];
int n;
for(i = 1; i <= 17; i++)
mny[i] = i * i;
while(scanf("%d", &n), n)
{
memset(f, 0, sizeof(f));
f[0] = 1;
for(i = 1; i <= 17; i++)
for(j = mny[i]; j <= n; j++)
f[j] += f[j - mny[i]];
printf("%d\n", f[n]);
}
//system("pause");
}
posted on 2012-08-15 14:12
小鼠标 阅读(280)
评论(0) 编辑 收藏 引用 所属分类:
DP