中国中信建设有限责任公司百度seo自然优化

两种递推细节不同

1,将1和n在序列末尾的情况单独放出来处理，因为dp[0]=0；

2,将所有情况统一处理，这种情况就要要求dp[1]=1;

这里的n在解题中可以看做是元素数量

思路是，根据出栈最后一个元素,统计它前面的元素数量的输出序列数和它后面的元素数量的输出序列数,因为他前面的必须先输出玩完，他才能放在栈底等最后一个出栈，然后他在栈底了，等它上面的都输出完，它最后出栈

#include <iostream>
#include <stack>
#include <algorithm>
#include<vector>
#include<unordered_map>
#include<set>
using namespace std;int main() {int n;cin >> n;int dp[19];dp[0] = 0;dp[1] = 1;//以出栈序列最后一个元素是几来进行划分for (int i = 2; i <= n; i++) {dp[i] = 2 * dp[i - 1];//最后出栈序列最后一个元素是1和nfor (int j = 2; j <= i - 1; j++) {dp[i] += dp[j - 1] * dp[i - j];//中间的数字是最后一个元素,它前面的元素的合法序列数量与它后面的元素合法序列数量相加，因为//该元素要最后一个出栈，所以它必须等它前面的元素也就是全部出完，数量是j-1，并且放在栈底，然后等它后面的元素全部出完，数量是i-j}}cout << dp[n];
}

#include <iostream>
#include <stack>
#include <algorithm>
#include<vector>
#include<unordered_map>
#include<set>
using namespace std;int main() {int n;cin >> n;int dp[19];dp[0] = 1;dp[1] = 1;//以出栈序列最后一个元素是几来进行划分for (int i = 2; i <= n; i++) {dp[i] = 0;for (int j = 1; j <= i ; j++) {dp[i] += dp[j - 1] * dp[i - j];}}cout << dp[n];
}