http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=2332
题目大意:(如题)
输入输出:(如题)
解题思路:
1.建立datv数组,用来记录所给的硬币种类。dp[j]表示构造数量为j的面值所用硬币的方式数。
2.当取用的第i种硬币,问题就转换为dp[j-datv[i]]这个子问题。即构造数量为j-datv[i]的面值所用硬币的方式数。
3.动态规划公式: dp[j]=dp[j]+dp[j-datv[i]](j>=datv[i])
                                dp[j]=dp[j](j<datv[i])
                                dp[j]=1(j=0)
4.输出dp[n]即为所求。
核心代码:

dp[0]=1;
	for(i=1;i<=v;i++)
		for(j=datv[i];j<=n;j++)
			dp[j]+=dp[j-datv[i]];

发表评论

电子邮件地址不会被公开。

Post Navigation