284. 金字塔

本文主要是介绍284. 金字塔，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

算法分析：
对于一棵树，其dfs序是固定序列，这个序列和树是对应的。因此，树的不少问题，都可以转化为序列求解。本题基本思路是这样的。

$f[i][j]$表示区间$[i,j]$构成的子树的不同结构数。这个状态只有在满足$s[i]=s[j]$的时候，才可能有意义，否则为0。

枚举断点$k$，$f[i][j]=f[i][j]+f[i+1][k-1]\ast f[k][j]$

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define ll long long int
const int P = 1000000000;
char s[310];
int n;
ll f[310][310];
int main()
{scanf("%s", s + 1);n = strlen(s + 1);memset(f, 0, sizeof(f));for (int i = 1; i <= n; ++i) f[i][i] = 1;for (int len = 2; len <= n; ++len)for (int i = 1; i < n; ++i){int j = i + len - 1;if (j > n) continue;if (s[i] == s[j]){for (int k = i + 2; k <= j; ++k)f[i][j] = (f[i][j] + f[i+1][k-1] * f[k][j]) % P;}}	printf("%lld\n", f[1][n]);return 0;
}

以下是记忆化搜索版本：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define ll long long int
const int P = 1000000000;
char s[310];
int n;
ll f[310][310];
ll dfs(int l, int r)
{if (l > r) return 0;if (l == r) return 1;if (s[l] != s[r]){f[l][r] = 0;return 0;}if (f[l][r] != -1) return f[l][r];f[l][r] = 0;for (int k = l + 2; k <= r; ++k)if (s[l] == s[k])f[l][r] = (f[l][r] + dfs(l+1, k-1) * dfs(k, r)) % P;return f[l][r];
}
int main()
{scanf("%s", s + 1);n = strlen(s + 1);memset(f, -1, sizeof(f));dfs(1, n);printf("%lld\n", f[1][n]);return 0;
}

这篇关于284. 金字塔的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---