hdu 1284 关于钱币兑换的一系列问题 九度oj 题目1408：吃豆机器人

钱币兑换问题

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 4565    Accepted Submission(s): 2576

Problem Description 在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。  

Input 每行只有一个正整数N，N小于32768。  

Output 对应每个输入，输出兑换方法数。  

Sample Input

2934
12553
        

Sample Output

718831
13137761
        

Author SmallBeer(CML)

这道题是典型的钱币兑换完全背包问题解决dp[i][j]代表前i种金钱在兑换数量为j的情况下的可能数

for(i=1;i<=c;i++)//c代表种类

for(j=0;j<=n;j++)//n代表兑换的金钱数

{

if(j<i)

dp[i][j]=dp[i-1][j];

else

dp[i][j]=dp[i][j-i]+dp[i-1][j];//关键就在这里dp[i][j]=(容量为j时装下第i种硬币的数量）+(容量为j不装下i种硬币的数量)

}

如果是01背包的那种只有1个的话就是

for(i=1;i<=c;i++)//c代表种类

for(j=0;j<=n;j++)//n代表兑换的金钱数

{

if(j<i)

dp[i][j]=dp[i-1][j];

else

dp[i][j]=dp[i-1][j-i]+dp[i-1][j];//第i件物品=（不选第i件，容量为j）+（选了i件，容量为j-i)

}

#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
int dp[4][32780];
int main()
{
	int i,j,n;
	dp[0][0]=1;
		for(i=1;i<=3;i++)
			for(j=0;j<=32770;j++)
			{
				
				if(j<i)
					dp[i][j]=dp[i-1][j];
				else
					dp[i][j]=dp[i][j-i]+dp[i-1][j];

			}
	while(scanf("%d",&n)!=EOF)
	{
	
			printf("%d\n",dp[3][n]);

	}
}
           

对空间进行优化，化为一维数组

#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
__int64 dp[35600];
int main()
{
	int i,j,n;	
	dp[0]=1;
		for(i=1;i<=3;i++)
			for(j=i;j<=35565;j++)//一维完全背包所以从[0,v]，二维从[v,1]开始
			{
			
					dp[j]+=dp[j-i];

			}
	while(scanf("%d",&n)!=EOF)
	{
			printf("%ld\n",dp[n]);

	}
}
           

对于理解这种类型的题介绍一种简单这种题，可以很好的理解这道题

点击打开链接

九度oj

题目1408：吃豆机器人

时间限制：1 秒

内存限制：32 兆

特殊判题：否

提交：823

解决：159

题目描述：

淘宝公司内部有许多新鲜的小玩具，例如淘宝智能机器人。小时候，大家都玩过那个吃豆子的游戏吧，这机器人就是按照这个游戏设计的，它会朝着豆子的方向行走。不过机器人还存在一个bug，他只会朝南和朝东走。现在有一块空地，分成了n*m个格子，每个格子内有一颗豆子。机器人的起点在西北角，终点在东南角。请问机器人从起点到终点有多少种不同的方法。

输入：

每个案例输入只有一行，有n和m两个正整数，n，m均小于等于10^3。由于答案很大，所以答案对10009取余。

输出：

对于每个案例，输出一行，输出机器人从起点到终点的总方法数。

样例输入：

2 23 3      

样例输出：

26      

这道题用网格的方法解释

f[n][m]=f[n-1][m]+f[n][m-1];可以很好的印证上面那道题

这道题让我知道了打表可以节省很多时间，如果不打表就过不了

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int dp[1005][1005];
int main()
{
int i,j,m,n;
memset(dp,0,sizeof(dp));
	//dp[0][1] = 1;
	for(i=1;i<=1002;i++)
		dp[i][1] = 1;
	for(i=1;i<=1002;i++)
		dp[1][i] = 1;
	for(i=2;i<=1002;i++)
		for(j=2;j<=1002;j++)
		{
			//dp[1][1]=1;
			dp[i][j]=(dp[i-1][j]+dp[i][j-1])%10009;
			//dp[i][j]=dp[i][j]%10009;
		}
while(scanf("%d%d",&m,&n)!=EOF)
{
		printf("%d\n",dp[m][n]);
}
return 0;
}