首先放上原題鏈接

點我，點我進入原題

什么是動態規劃？

在這類問題中，可能會有許多可行解。每一個解都對應于一個值，我們希望找到具有最優值的解。而且每次求出的解不是獨立的，我們需要逐層推出最優解。
以這道題為例，題目要求整棵二叉樹加分最大，并且分數=左子樹分數* 右子樹分數+自身數值，這就需要使左右子樹分數盡可能大->左右子樹的子樹要大，所以我們就需要選取一個合適的根節點。并且求出此時的最大分數。

求解過程

接著就是求解動態規劃的狀態轉移方程了。
我們其實就可以將題目看做求[i,j]這個區間里的最大值，這樣就可以得出狀態轉移方程

f[i][j]=max{f[i][k-1]*f[k+1][j]+f[k][k] | i<=k<=j}//i,j是區間范圍，k為根節點

題目還要求先序遍歷輸出，所以我們還需要一個root[i][j]數組來表示節點i到節點j成樹的最大加分所選的根節點。

下面上代碼進行分析

#include <iostream> using namespace std; long long n; long long f[100][100],root[100][100];//創建所需要的f和root數組 void xianxu(long long ,long long );//先序遍歷的函數 int main() {int i,len,j;cin>>n;for(i=1;i<=n;i++)//因為中序遍歷從1開始的，所以從1開始有很好的對應性{cin>>f[i][i];//將分數值存儲到相應的f里root[i][i]=i;//中序的遍歷的數據}for(len=1;len<n;len++){for(i=1;i+len<=n;i++)//多次取范圍，求取符合f[i][k-1]*f[k+1][j]+f[k][k]最大的情況{j=i+len;//范圍的右邊界f[i][j]=f[i+1][j]+f[i][i];//易知當有左子樹時，不會是最優解，所以最大值先先賦值為根+右子樹的分數root[i][j]=i;//默認設置根為第一個值for(int k=i+1;k<j;k++)//當根為第二個，第三個……直到范圍邊界{if(f[i][j]<f[i][k-1]*f[k+1][j]+f[k][k])//計算當前取的根的情況下，f[i][j]是否為當前的最大值{f[i][j]=f[i][k-1]*f[k+1][j]+f[k][k];//如果是，f[i][j]里的最大值就賦值root[i][j]=k;//記錄取最大值時的根}}}}cout<<f[1][n]<<endl;//輸出題目要求的[1,n]的最大值xianxu(1,n);//進行先序遍歷return 0; } void xianxu(long long l,long long r) {if(l>r)//當左邊比右邊大時，進行回溯{return;}cout<<root[l][r]<<" ";//輸出先序遍歷輸出if(l==r)//左右相等時回溯{return;}xianxu(l,root[l][r]-1);//遍歷左子樹xianxu(root[l][r]+1,r);//遍歷右子樹 }

至此完結

總結

以上是生活随笔為你收集整理的洛谷P1040 加分二叉树运用区间DP（动态规划）求解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。