hdu 1267 下沙的沙子有几粒？(递推&DP)

96 阅读 0 评论 64 点赞

我是靠谱客的博主忧伤蜜蜂，最近开发中收集的这篇文章主要介绍hdu 1267 下沙的沙子有几粒？(递推&DP)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

根据题目输入的是 H 和 D 的个数，用a [ i ] [ j ]代表有i个 H 和j个 D 的序列的种数。
考虑最后一个字母是 H 还是 D 的情况，最后一个字母是 D 的情况的序列种数是a [ i ][ j-1 ]，最后一个字母是 H 的情况的序列种数是a [ i-1 ][ j ]。

则：a [ i ][ j ] = a [ i-1 ][ j ] + a [ i ][ j-1 ]；

#include<stdio.h>
#include<iostream>
using namespace std;
long long dp[30][30];
void fun(){
int i,j;
for(i=0;i<=20;i++){
dp[i][0]=1;
}
for(j=1;j<=20;j++){
for(i=j;i<=20;i++){
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
}
int main(){
int n,m,i,j;
fun();
while(~scanf("%d%d",&n,&m)){
printf("%I64dn",dp[n][m]);
}
return 0;
}