在 C++ 算法的浩瀚宇宙中，樹與圖就像是神秘的迷宮和茂密的森林，充滿了未知與挑戰。而動態規劃則是我們探索其中的神奇羅盤，幫助我們找到最優路徑。今天，就讓我們一起深入這片神秘領域，揭開樹與圖上動態規劃的神秘面紗！?

樹與圖上動態規劃的獨特魅力?

與線性動態規劃相比，樹與圖上的動態規劃更加復雜，因為它們的結構不再是簡單的線性，而是具有分支和循環。但正是這種復雜性，讓它們能夠解決更多現實世界中的問題，比如城市交通網絡的最優路線規劃、社交網絡中的信息傳播分析等。在樹與圖上使用動態規劃，就像是在錯綜復雜的迷宮中，通過標記一個個關鍵點（狀態），找到從起點到終點的最佳路徑（最優解）。?

樹結構上的動態規劃?

樹結構天然具有遞歸和層次的特性，這使得樹的動態規劃通常從葉子節點向根節點進行狀態轉移。我們以 “樹的最大路徑和” 問題為例來深入理解。?

問題描述?

給定一棵二叉樹，找到從樹中某個節點到其他節點的路徑中，節點值之和最大的路徑。路徑可以從任意節點開始，到任意節點結束。?

代碼示例?

#include <iostream>
#include <algorithm>
using namespace std;// 定義二叉樹節點結構
struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};int maxPathSum(TreeNode* root, int& maxSum) {if (root == nullptr) {return 0;}// 遞歸計算左子樹的最大貢獻值int leftMax = max(0, maxPathSum(root->left, maxSum));// 遞歸計算右子樹的最大貢獻值int rightMax = max(0, maxPathSum(root->right, maxSum));// 計算經過當前節點的路徑和int currentPathSum = root->val + leftMax + rightMax;// 更新全局最大路徑和maxSum = max(maxSum, currentPathSum);// 返回當前節點能為父節點提供的最大貢獻值return root->val + max(leftMax, rightMax);
}int maxPathSum(TreeNode* root) {int maxSum = INT_MIN;maxPathSum(root, maxSum);return maxSum;
}

代碼解釋?

1. 首先定義了二叉樹節點的結構體 TreeNode ，包含節點值 val 以及左右子節點指針 left 和 right 。?

1. maxPathSum(TreeNode* root, int& maxSum) 函數用于遞歸計算以 root 為根節點的子樹的最大路徑和。它有兩個返回值相關的操作：?

• 函數內部計算當前節點能為父節點提供的最大貢獻值。這是通過比較左子樹和右子樹的最大貢獻值（如果為負數則取 0，因為負數不會增加路徑和的大小），再加上當前節點的值得到的。比如，leftMax = max(0, maxPathSum(root->left, maxSum)); 就是計算左子樹的最大貢獻值。?

• 同時，計算經過當前節點的路徑和，即當前節點值加上左子樹和右子樹的最大貢獻值，如 int currentPathSum = root->val + leftMax + rightMax; ，并更新全局最大路徑和 maxSum 。?

1. 外層的 maxPathSum(TreeNode* root) 函數初始化全局最大路徑和為最小值 INT_MIN ，然后調用內部遞歸函數計算并返回最終的最大路徑和。?

圖結構上的動態規劃?

圖的動態規劃通常需要處理節點之間復雜的連接關系，常見的有拓撲排序結合動態規劃來解決有向無環圖的問題，或者使用記憶化搜索處理一般圖。我們以 “有向無環圖的最長路徑” 問題為例。?

問題描述?

給定一個有向無環圖（DAG），圖中節點帶有權值，找到從某個起點到其他節點的最長路徑長度。?

代碼示例?

#include <iostream>
#include <vector>
#include <queue>
using namespace std;// 拓撲排序 + 動態規劃求有向無環圖的最長路徑
int longestPathInDAG(vector<vector<pair<int, int>>>& graph, int start) {int n = graph.size();vector<int> indegree(n, 0);  // 入度數組vector<int> dp(n, 0);  // dp[i]表示從起點到節點i的最長路徑長度queue<int> q;// 統計每個節點的入度for (int i = 0; i < n; ++i) {for (auto& edge : graph[i]) {indegree[edge.first]++;}}// 將入度為0的節點入隊for (int i = 0; i < n; ++i) {if (indegree[i] == 0) {q.push(i);}}while (!q.empty()) {int node = q.front();q.pop();for (auto& edge : graph[node]) {int nextNode = edge.first;int weight = edge.second;// 更新到下一個節點的最長路徑長度dp[nextNode] = max(dp[nextNode], dp[node] + weight);indegree[nextNode]--;if (indegree[nextNode] == 0) {q.push(nextNode);}}}int maxPath = 0;for (int i = 0; i < n; ++i) {maxPath = max(maxPath, dp[i]);}return maxPath;
}

代碼解釋?

1. 首先定義了圖的存儲結構 vector<vector<pair<int, int>>> ，其中 graph[i] 存儲了節點 i 所有的出邊，每個 pair 表示目標節點和邊的權值。?

1. 使用 indegree 數組統計每個節點的入度，dp 數組用于記錄從起點到每個節點的最長路徑長度。?

1. 通過拓撲排序將入度為 0 的節點入隊，然后不斷從隊列中取出節點，更新其鄰接節點的最長路徑長度（如 dp[nextNode] = max(dp[nextNode], dp[node] + weight); ），并減少鄰接節點的入度。當鄰接節點入度變為 0 時，將其入隊。?

1. 最后遍歷 dp 數組，找出最長路徑長度并返回。?

樹與圖上的動態規劃充滿了挑戰與樂趣，它們在數據結構和算法的世界中扮演著重要角色。通過不斷練習和思考，你會發現自己在這片神秘領域中越來越游刃有余。快去探索更多有趣的問題，用動態規劃解開它們的奧秘吧！?