题目描述

思路分析

实现代码

• 不过我的代码写的真的不够简洁，逻辑不够清晰，后续多练练吧。

// 组合数问题
#include <iostream>
#include <algorithm>using namespace std;const int N = 35;
int n,f[N][N],g[N][N],w[N];
// f[i][j]表示区间i到j的构成的二叉树最大的加数
// g[i][j]表示区间i到j的构成最大加数二叉树的根节点的坐标
// w[i]表示第i个节点的权值void dfs(int l,int r){if(l > r) return;int k = g[l][r];cout<<k<<" ";dfs(l,k-1);dfs(k + 1,r);}int main(){cin>>n;for(int i = 1;i <= n;i ++) cin>>w[i];// 遍历区间的长度for (int len = 1; len <= n; ++len) {// 遍历区间左端点for (int i = 1; i + len - 1 <= n ; ++i) {int j = i + len -1;// 左右节点相等，不用额外尽心遍历if (i == j) f[i][j] = w[i],g[i][j] = i;else{// 遍历划分节点,总共是三种情况for (int k = i; k <= j; ++k) {int score = 0;if (k == i){// 划分节点在左端点，没有左子节点score = w[k] + f[ k + 1][j];}else if (k == j){// 划分节点在右端点，没有右子节点score = w[k] + f[i][k - 1];}else{// 划分节点在中间，左右子节点都有score = w[k] + f[i][k - 1] * f[k + 1][j];}// 记录顶点节点if(f[i][j] < score) {f[i][j] = score;g[i][j] = k;}}}}}cout<<f[1][n]<<endl;dfs(1,n);};

分析总结

• 在这里要知道一些关于前序、后序还有中序转换的问题，既然考到了，但是我一点都想不起来。
• 思路分析很重要