資訊專欄INFORMATION COLUMN
摘要：動態規劃練習題匯總描述有堆石子排成一排，每堆石子有一定的數量。現要將堆石子并成為一堆。合并的過程只能每次將相鄰的兩堆石子堆成一堆，每次合并花費的代價為這兩堆石子的和，經過次合并后成為一堆。
動態規劃練習題匯總
描述
有N堆石子排成一排，每堆石子有一定的數量。現要將N堆石子并成為一堆。合并的過程只能每次將相鄰的兩堆石子堆成一堆，每次合并花費的代價為這兩堆石子的和，經過N-1次合并后成為一堆。求出總的代價最小值。
輸入
序列n，序列值表示第i堆石子的數量，0<=i
輸出總代價的最小值
1 思路
最先合并的石子堆在后期中可能被多次合并，因此最先合并的石子堆數量越小越好
2 拆分子問題
每次進行合并，需要從當前的石子堆中選取兩個相鄰的石子數量和最少的作為被合并的堆
3 計算 4 代碼 recursive DP 5 時間復雜度
令第i次合并后的總代價為C(i)，C(0)=0，則C(i+1)=C(i)+min{序列[k]+序列[k+1]}，其中 0<=i
bottom-up DPconst stoneArray = [4, 2, 3, 9, 6, 8, 1, 7];
class CalStone {
constructor(options) {
this.stoneArray = Array.isArray(options) ? options : [];
}
getStoreBottomUp() {
let i = 0;
const len = this.stoneArray.length;
while (++i < len) {
let min = { sum: 99999999999, index: [-1, -1] };
for (let i = 0; i < this.stoneArray.length - 1;i++){
const sum = this.stoneArray[i] + this.stoneArray[i + 1];
min = sum < min.sum ? { sum: sum, index: [i, i + 1] } : min;
}
this.stoneArray = [].concat(this.stoneArray.slice(0, min.index[0]), min.sum, this.stoneArray.slice(min.index[1]+1));
}
console.log(`總代價為 ${this.stoneArray[0]}`);
}
}
new CalStone(stoneArray).getStoreBottomUp();
const stoneArray = [4, 2, 3, 9, 6, 8, 1, 7];
class CalStone {
constructor(options) {
this.stoneArray = Array.isArray(options) ? options : [];
}
getStoneRecursive(arr = this.stoneArray) {
if (arr.length === 1) {
console.log(`總代價為 ${arr[0]}`);
return arr;
} else {
let min = { sum: 99999999999, index: [-1, -1] };
for (let i = 0; i < arr.length - 1; i++) {
const sum = arr[i] + arr[i + 1];
min = sum < min.sum ? { sum: sum, index: [i, i + 1] } : min;
}
const newStoneArr = [].concat(arr.slice(0, min.index[0]), min.sum, arr.slice(min.index[1] + 1));
return this.getStoneRecursive(newStoneArr);
}
}
}
new CalStone(stoneArray).getStoneRecursive();
需要進行n-1次合并，第i次合并需要進行n-i次比較，故時間復雜度為O(n2)
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/110004.html
摘要：動態規劃練習題匯總題目描述傳說中的九頭龍是一種特別貪吃的動物。如上圖中的輸出輸出一個整數，表示在滿足大頭的要求的前提下，九頭龍的難受值的最小值。 動態規劃練習題匯總 題目描述傳說中的九頭龍是一種特別貪吃的動物。雖然名字叫九頭龍，但這只是說它出生的時候有九個頭，而在成長的過程中，它有時會長出很多的新頭，頭的總數會遠大于九，當然也會有舊頭因衰老而自己脫落。有一天，有M個腦袋的九頭龍看到一棵...
摘要：動態規劃練習題總題目描述設一個個節點的二叉樹的中序遍歷為，其中數字為節點編號。若某個子樹為空，規定其加分為，葉子的加分就是葉節點本身的分數。試求一棵符合中序遍歷為且加分最高的二叉樹。 動態規劃練習題-總 題目描述設一個n個節點的二叉樹tree的中序遍歷為（1,2,3,…,n），其中數字1,2,3,…,n為節點編號。每個節點都有一個分數（均為正整數），記第i個節點的分數為di，tree及...
馬上就要開始啦這次共組織15個組隊學習 涵蓋了AI領域從理論知識到動手實踐的內容 按照下面給出的最完備學習路線分類 難度系數分為低、中、高三檔 可以按照需要參加 - 學習路線 - showImg(https://segmentfault.com/img/remote/1460000019082128); showImg(https://segmentfault.com/img/remote/...
閱讀 788·2021-10-09 09:44
閱讀 692·2019-08-30 13:55
閱讀 3153·2019-08-29 15:07
閱讀 3218·2019-08-29 13:09
閱讀 2413·2019-08-29 11:10
閱讀 1289·2019-08-26 14:05
閱讀 3591·2019-08-26 13:57
閱讀 2206·2019-08-23 16:42
