在写题解之前给自己打一下广告哈~。。抱歉了，希望大家多多支持我在CSDN的视频课程，地址如下：

http://edu.csdn.net/course/detail/209

题目：

1 1
3 1

1
3

            就是给你m个H和n个D，然后从左开始数H的累积个数总是不比D的累计数少的排列有多少种举一个测试案例吧：3个H和1个D总共有3种排列，依次是：H D H H,H H D H,H H  H D三种排列，

题目分析：

              简单DP。题目一开始又扯了一大堆有的没的。。。。。。其实题目就是说“有m个H，n个D，且任意索引上H的个数都不小于D的个数，问这样的方案数有多少种”。

递推公式是: a[m][n] = a[m-1][n] + a[m][n-1] 。前面代表的是H的个数.后面代表的是D的个数。

               推导过程如下：然后当n=0的时候无论m取何值都是1，递推公式怎么推来的呢？我现在说下我的思路吧！假设3个H和2个D是由2个H和2个D还有3个H一个D推来的，2个H和2个D总共有H D H D，H H D D两种排列，3个H和一个D总共有H D H H,H H D H,H H  H D三种排列，然后在H D H D，H H D D的后面添加一个H就是2中排列，在H D H H,H H D H,H H  H D的后面添加一个D就有3种方案，所以总共就是5种方案（其它的添加方法都是重复的，不信的话自己可以试一下）

代码如下：

/*
* d.cpp
*
*
Created on: 2015年2月4日
*
Author: Administrator
*/
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 21;
long long a[maxn][maxn];
void prepare() {
int i;
for (i = 0; i < maxn; ++i) {
a[i][0] = 1;//当D的个数为0时，无论多少个H,它的排列数都只有一种.
}
//需要注意的是,这里a[0][i] = 0 .没初始化,因为默认值就是0.因为没有H,这种方案就不成立了
int j;
for (i = 1; i < maxn; ++i) {
for (j = i; j < maxn; ++j) {
a[j][i] = a[j - 1][i] + a[j][i - 1];
}
}
}
int main() {
prepare();
int n, m;
while (scanf("%d%d", &n, &m) != EOF) {
printf("%lldn", a[n][m]);
}
return 0;
}

最后

以上就是调皮八宝粥为你收集整理的(hdu step 2.3.7)下沙的沙子有几粒？(简单DP:求有m个H,n和D，且任意索引上H的个数都要比D的个数多的方案数)下沙的沙子有几粒？的全部内容，希望文章能够帮你解决(hdu step 2.3.7)下沙的沙子有几粒？(简单DP:求有m个H,n和D，且任意索引上H的个数都要比D的个数多的方案数)下沙的沙子有几粒？所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。