题目大意:从队首报数到n,每次最多报m个人,共有多少方案
思路:首先,找递推式,每次第一个人直接到后面m个人把到达第一个人的方案数加给后面那些人(其实这样的思路逆过来想就是你要找到达第n个人方案数,你必定要找到达这个人的前m个人分别的方案数,把到达这些人的方案数加给n,然后分别去找这m个人的前m个人的方案数加给他,但只要超过队首就不执行,这里面存在着递归思想,我们用数组递推也就是所谓的动态规划)
代码如下:
1.从队前往队后操作:
#include<stdio.h>
#include<string.h>
int main()
{
int i,j,n,m,dp[40];
while(~scanf("%d%d",&n,&m)&&(n||m))
{
memset(dp,0,sizeof(dp));
dp[0]=1;
for(i=0;i<n;i++)
for(j=i+1;j<=m+i&&j<n;j++)
{
dp[j]+=dp[i];
}
printf("%d\n",dp[n-1]);
}
return 0;
}
2.从队后往队前要递归,代码还没想好