亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

動態(tài)規(guī)劃練習題-石子合并

ziwenxie / 1354人閱讀

摘要：動態(tài)規(guī)劃練習題匯總描述有堆石子排成一排，每堆石子有一定的數(shù)量?，F(xiàn)要將堆石子并成為一堆。合并的過程只能每次將相鄰的兩堆石子堆成一堆，每次合并花費的代價為這兩堆石子的和，經過次合并后成為一堆。

動態(tài)規(guī)劃練習題匯總

描述
有N堆石子排成一排，每堆石子有一定的數(shù)量?，F(xiàn)要將N堆石子并成為一堆。合并的過程只能每次將相鄰的兩堆石子堆成一堆，每次合并花費的代價為這兩堆石子的和，經過N-1次合并后成為一堆。求出總的代價最小值。
輸入
序列n，序列值表示第i堆石子的數(shù)量，0<=i輸出
輸出總代價的最小值

1 思路
最先合并的石子堆在后期中可能被多次合并，因此最先合并的石子堆數(shù)量越小越好

2 拆分子問題
每次進行合并，需要從當前的石子堆中選取兩個相鄰的石子數(shù)量和最少的作為被合并的堆

3 計算
令第i次合并后的總代價為C(i)，C(0)=0，則C(i+1)=C(i)+min{序列[k]+序列[k+1]}，其中 0<=i

4 代碼
bottom-up DP

const 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();

recursive DP

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();

5 時間復雜度
需要進行n-1次合并，第i次合并需要進行n-i次比較，故時間復雜度為O(n2)

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://www.ezyhdfw.cn/yun/110004.html

相關文章

  • 動態(tài)規(guī)劃練習題-總

    摘要：最近學習了動態(tài)規(guī)劃的四節(jié)網(wǎng)課，想上手練習，故寫文章留作紀念，文章的主要內容是解題思路，代碼用寫練習題分為四種，線性動規(guī)攔截導彈，合唱隊形，挖地雷，建學校，劍客決斗等，區(qū)域動規(guī)石子合并，加分二叉樹，統(tǒng)計單詞個數(shù)，炮兵布陣等，樹形動規(guī)貪吃的九頭 最近學習了動態(tài)規(guī)劃的四節(jié)網(wǎng)課，想上手練習，故寫文章留作紀念，文章的主要內容是解題思路，代碼用JS寫 練習題分為四種：1，線性動規(guī)：攔截導彈，合唱隊...

    yacheng 評論0 收藏0

  • 動態(tài)規(guī)劃練習題-貪吃的九頭龍

    摘要：動態(tài)規(guī)劃練習題匯總題目描述傳說中的九頭龍是一種特別貪吃的動物。如上圖中的輸出輸出一個整數(shù)，表示在滿足大頭的要求的前提下，九頭龍的難受值的最小值。 動態(tài)規(guī)劃練習題匯總 題目描述傳說中的九頭龍是一種特別貪吃的動物。雖然名字叫九頭龍，但這只是說它出生的時候有九個頭，而在成長的過程中，它有時會長出很多的新頭，頭的總數(shù)會遠大于九，當然也會有舊頭因衰老而自己脫落。有一天，有M個腦袋的九頭龍看到一棵...

    MockingBird 評論0 收藏0

  • 動態(tài)規(guī)劃練習題-加分二叉樹

    摘要：動態(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及...

    Miracle 評論0 收藏0

  • 第7期 Datawhale 組隊學習計劃

    馬上就要開始啦這次共組織15個組隊學習 涵蓋了AI領域從理論知識到動手實踐的內容 按照下面給出的最完備學習路線分類 難度系數(shù)分為低、中、高三檔 可以按照需要參加 - 學習路線 - showImg(https://segmentfault.com/img/remote/1460000019082128); showImg(https://segmentfault.com/img/remote/...

    dinfer 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<