Problem Description

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

 

Input

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

 

Output

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

 

Sample Input

 

Sample Output

 

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种硬币的数量)
}

#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;

}