資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
安卓
Python
C 程式設計
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會科學
時尚研究
法律研究二叉樹中兩個節點不相鄰時的最大節點和 | C++ 中的動態規劃
在本文中，我們將討論一個程式，利用動態規劃求二叉樹中最大和節點，且要求任意兩個節點不直接連線。
為此，我們將給出一個二叉樹。我們的任務是利用動態規劃，找到和最大的子集，且該子集中任意兩個節點不直接連線。
示例
#include <bits/stdc++.h>
using namespace std;
//finding diameter using dynamic programming
void dfs(int node, int parent, int dp1[], int dp2[], list<int>* adj, int tree[]){
int sum1 = 0, sum2 = 0;
for (auto i = adj[node].begin(); i != adj[node].end();
++i) {
if (*i == parent)
continue;
dfs(*i, node, dp1, dp2, adj, tree);
sum1 += dp2[*i];
sum2 += max(dp1[*i], dp2[*i]);
}
dp1[node] = tree[node] + sum1;
dp2[node] = sum2;
}
int main() {
int n = 5;
list<int>* adj = new list<int>[n + 1];
adj[1].push_back(2);
adj[2].push_back(1);
adj[1].push_back(3);
adj[3].push_back(1);
adj[2].push_back(4);
adj[4].push_back(2);
adj[2].push_back(5);
adj[5].push_back(2);
int tree[n + 1];
tree[1] = 10;
tree[2] = 5;
tree[3] = 11;
tree[4] = 6;
tree[5] = 8;
int dp1[n + 1], dp2[n + 1];
memset(dp1, 0, sizeof dp1);
memset(dp2, 0, sizeof dp2);
dfs(1, 1, dp1, dp2, adj, tree);
cout << "Maximum sum: " << max(dp1[1], dp2[1]) << endl;
return 0;
}輸出
Maximum sum: 25
更新於： 2020 年 9 月 8 日
75 次瀏覽
Advertisement 廣告