如果用f [ i ] [ j ]代表有i个H和j个D的序列的种数,则:
f [ i ][ j ] = f [ i-1 ][ j ] + f [ i ][ j-1 ];
考虑最后一个字母是H还是D的情况,最后一个字母是D的情况的序列种数是f [ i ][ j-1 ],最后一个字母是H的情况的序列种数是f [ i-1 ][ j ]。
#include <iostream>
#include <cstdio>//包含此头文件是为了调用C风格的输出函数printf.
using namespace std;
int main()
{
__int64 a[21][21]={0};//也可以用memset(a,0,sizeof(a))需要包含头文件<cstring>
//不过我刚刚测试了一下,不包含头文件<string.h>或者<memory.h>也没有关系。不懂!
//甚至不初始化,该题也能AC!!!
int i,j;
for(i=0;i<=20;i++)
{
a[i][0]=1;//只要‘D’的个数为0,‘H’的个数为任意数,都是一种序列
a[0][i]=0;//只要‘H’的个数为0,‘D’的个数为任意数,这种序列都不满足
}
for(i=1;i<=20;i++)
for(j=1;j<=20;j++)
{
if(i<j) //遇到‘H’个数少于‘D’个数时,这种序列不满足。
a[i][j]=0;
else //‘H’个数大于或者等于‘D’个数时,进入状态转移方程
a[i][j]=a[i-1][j]+a[i][j-1];///DP核心
}
int m,n;
while(cin>>m>>n)
{
printf("%I64d\n",a[m][n]);
}
return 0;
}