（动态规划+卡特兰数）洛谷1044 栈
·
题目概述：
源代码：
#include<iostream>
using namespace std;
#define maxn 19
int dp[maxn];
int main()
{
std::ios::sync_with_stdio(false);
int n;
cin >> n;
dp[0] = 1, dp[1] = 1;
for (int i = 2; i<=n;++i)
for (int j = 0; j <= i; ++j)
{
dp[i] += (dp[j] * dp[i - j-1]);
}
cout << dp[n] << endl;
return 0;
}
分析思路：
1.直觉判断，数目为n的元素入栈出栈方法和n-1数目入栈方法有联系，应想到动态规划。
2.比如对于n=3的情况，可以把他看作f[0]*f[2]+f[1]*f[1],从而得到递归关系，f[i]=f[0]*f[i-1]+f[1]+f[i-2]+......+f[i-1]*f[0];
3.查阅资料发现与数论有关，引入卡特兰数的概念：
这题暗含了最原始的1号公式，但是其他公式也有记忆的必要。
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
0
0- 0
已为社区贡献1条内容
所有评论(0)