HDU 下沙的沙子有几粒？（递推）

写一下自己的思路历程。。
1.类比leetcode的括号匹配，采用dfs（当H的数目大于D的数目且D的数目小于n时，在字符串尾增加一个D)当H的数目小于m时，在子串增加一个H；结束搜索的条件是D的数目等于n且H的数目等于m，结束时检查得到字符串是不是符合要求，如果是则ans++；最后输出ans
结果是交上去血T；
由此想到第二种做法，由于n,m都不大，最多209个测试用例，因此想到可以打表来做
2.dfs + 打表
结果：在n = 15，m = 16的时候已经非常慢了，等不下去了。。。
3.递推
不过观察之前的打表结果（自己想也可知）
如果我们用dp[i][j]来表示使用i个H，和j个D所能得到的最大方案数，那么其来源只有两个，第一个是在i >= j + 1的时候 加上的dp[i - 1][j]（表示在使用i - 1个H的基础上末尾添加一个H） 另外一个是在i >= j - 1的时候加上dp[i][j - 1](表示在使用j - 1个D的基础上再添加一个D）
于是先把表打好；对于每个询问使用o(1)的时间输出答案即可。。

#include <bits/stdc++.h>
using namespace std;
long long dp[30][30];
int m,n;
int main()
{
for(int i = 1; i <= 20; i++) dp[i][1] = i;
for(int i = 1; i <= 20; i++)
{
for(int j = 2; j <= i; j++)
{
if(i >= j + 1)
{
dp[i][j] += dp[i - 1][j];
}
if(i >= j - 1)
{
dp[i][j] += dp[i][j - 1];
}
}
}
while(~scanf("%d %d",&m,&n))
{
cout << dp[m][n] << endl;
}
return 0;
}

最后

以上就是愤怒树叶为你收集整理的HDU 下沙的沙子有几粒？（递推）的全部内容，希望文章能够帮你解决HDU 下沙的沙子有几粒？（递推）所遇到的程序开发问题。

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