資訊專欄INFORMATION COLUMN
摘要：動態(tài)規(guī)劃練習題總題目描述設一個個節(jié)點的二叉樹的中序遍歷為，其中數(shù)字為節(jié)點編號。若某個子樹為空，規(guī)定其加分為，葉子的加分就是葉節(jié)點本身的分數(shù)。試求一棵符合中序遍歷為且加分最高的二叉樹。
動態(tài)規(guī)劃練習題-總
題目描述
設一個n個節(jié)點的二叉樹tree的中序遍歷為（1,2,3,…,n），其中數(shù)字1,2,3,…,n為節(jié)點編號。每個節(jié)點都有一個分數(shù)（均為正整數(shù)），記第i個節(jié)點的分數(shù)為di，tree及它的每個子樹都有一個加分，任一棵子樹subtree（也包含tree本身）的加分計算方法如下：
subtree的左子樹的加分× subtree的右子樹的加分＋subtree的根的分數(shù)。
若某個子樹為空，規(guī)定其加分為1，葉子的加分就是葉節(jié)點本身的分數(shù)。不考慮它的空子樹。
試求一棵符合中序遍歷為（1,2,3,…,n）且加分最高的二叉樹tree。要求輸出tree的最高加分和前序遍歷
輸入
長度為n的序列，序列值為每個節(jié)點的分數(shù)（分數(shù)＜100）如：5,7,1,2,10
輸出
最高加分；前序遍歷，如：145; 3 1 2 4 5
1 思路
若要使加分最高，則需讓父節(jié)點盡可能小
2 拆分子問題
構建樹的過程中，從當前序列找到值最小的節(jié)點作為父節(jié)點，節(jié)點左側序列為左子樹，右側序列為右子樹
3 計算
T[0,m]={ Node[k], left:T[0,k-1], right:T[k+1,m]}
4 代碼
recursive DP
const treeArray = [5,7,1,2,10];
class CalTree {
constructor(options) {
this.treeArray = Array.isArray(options) ? options : [];
this.walkArr = [];
this.sum = 0;
}
getTreeRecursive() {
const newArr = this.getTreeRec(this.treeArray);
this.sum = this.getSum(newArr);
console.log(`前序遍歷序列是: ${ this.walkArr.join(",") }`);
console.log(`最高加分是 ${this.sum}`); // 最高得分
}
getTreeRec(arr) {
const min = Math.min(...arr);
const item = {
value: min,
index: arr.indexOf(min)
};
if (arr.length === 1) {
return {
item,
left: null,
right: null
};
}
const leftArr = arr.slice(0, item.index);
const rightArr = arr.slice(item.index + 1, arr.length);
let obj = {};
obj.item = item;
obj.left = leftArr.length > 0 ? this.getTreeRec(leftArr):null;
obj.right = rightArr.length > 0 ? this.getTreeRec(rightArr) : null;
return obj;
}
getSum(obj) {
this.walkArr.push(obj.item.value);
if (!obj.left && !obj.right) {
return obj.item.value;
}
const left = obj.left ? this.getSum(obj.left) : 1;
const right = obj.right ? this.getSum(obj.right) : 1;
return obj.item.value + left * right;
}
}
new CalTree(treeArray).getTreeRecursive();
5 時間復雜度
主要過程是把序列一分為二分別建子樹，第i次拆分的計算量是2的i次方，故時間復雜度為O(2的logn次方)
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉載請注明本文地址：http://systransis.cn/yun/110053.html
摘要：最近學習了動態(tài)規(guī)劃的四節(jié)網課，想上手練習，故寫文章留作紀念，文章的主要內容是解題思路，代碼用寫練習題分為四種，線性動規(guī)攔截導彈，合唱隊形，挖地雷，建學校，劍客決斗等，區(qū)域動規(guī)石子合并，加分二叉樹，統(tǒng)計單詞個數(shù)，炮兵布陣等，樹形動規(guī)貪吃的九頭 最近學習了動態(tài)規(guī)劃的四節(jié)網課，想上手練習，故寫文章留作紀念，文章的主要內容是解題思路，代碼用JS寫 練習題分為四種：1，線性動規(guī)：攔截導彈，合唱隊...
摘要：很多前端同學在看到數(shù)據(jù)結構和算法后會有一定的抵觸心理，或者嘗試去練習，但是被難倒，從而放棄。本文選擇的數(shù)據(jù)結構和算法的類別均是出現(xiàn)頻率最高，以及應用最廣的類別。面試這是非常現(xiàn)實的一點，也是很多前端學習數(shù)據(jù)結構和算法的原因。 一、導讀 據(jù)我了解，前端程序員有相當一部分對數(shù)據(jù)結構和算法的基礎概念都不是很清晰，這直接導致很多人在看到有關這部分的內容就會望而卻步。 實際上，當你了解了數(shù)據(jù)結構和...
摘要：上一篇數(shù)據(jù)結構與算法集合字典一遞歸學習樹離不開遞歸。先序遍歷的一種應用是打印一個結構化的文檔下面的圖描繪了先序遍歷方法的訪問路徑后序遍歷后序遍歷則是先訪問節(jié)點的后代節(jié)點，再訪問節(jié)點本身。 上一篇：JS數(shù)據(jù)結構與算法_集合&字典 一、遞歸 學習樹離不開遞歸。 1.1 介紹 遞歸是一種解決問題的方法，它解決問題的各個小部分，直到解決最初的大問題。遞歸通常涉及函數(shù)調用自身。 通俗的解釋：年級...
閱讀 2934·2021-11-24 09:39
閱讀 3619·2021-11-22 13:54
閱讀 3419·2021-11-16 11:45
閱讀 2449·2021-09-09 09:33
閱讀 3203·2019-08-30 15:55
閱讀 1298·2019-08-29 15:40
閱讀 928·2019-08-29 15:19
閱讀 3406·2019-08-29 15:14
