HDU--1267--递推

186 阅读 0 评论 123 点赞

我是靠谱客的博主专注野狼，这篇文章主要介绍HDU--1267--递推，现在分享给大家，希望可以做个参考。

问题描述：假定一个字符串由m个H和n个D组成，从左到右扫描该串，如果字符H的累计数总是不小于字符D的累计数,那么，满足条件的字符串总数。

思路：递推+long long 处理

a[i][0]:表示HHH....此时的情况为1，则a[i][0]=1;

a[0][i]:表示...DDD,此时的情况为0，则a[0][i]=0;

a[i][j]=a[i-1][j]+a[i][j-1],此时表示一般情况下相加，其中j<=i;

代码如下：

Sample Input
1 1
3 1
Sample Output
1
3

#include<iostream>
#include<cstring>
using namespace std;
int main(){
long long int a[25][25];
int i,j,m,n;
memset(a,0,sizeof(a));
for(i=1;i<=20;i++)
a[i][0]=1;
for(i=1;i<=20;i++)
for(j=1;j<=i;j++)
a[i][j]=a[i-1][j]+a[i][j-1];//跑楼梯
while(scanf("%d %d",&m,&n)!=EOF)
printf("%lldn",a[m][n]);
}
/*Sample Input
1 1
3 1
Sample Output
1
3*/