国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

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

ziwenxie / 1294人閱讀

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

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

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

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

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

3 計(jì)算
令第i次合并后的總代價(jià)為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(`總代價(jià)為 ${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(`總代價(jià)為 ${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 時(shí)間復(fù)雜度
需要進(jìn)行n-1次合并，第i次合并需要進(jìn)行n-i次比較，故時(shí)間復(fù)雜度為O(n2)

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

轉(zhuǎn)載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/110004.html

相關(guān)文章

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

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

    yacheng 評論0 收藏0

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

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

    MockingBird 評論0 收藏0

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

    摘要：動態(tài)規(guī)劃練習(xí)題總題目描述設(shè)一個(gè)個(gè)節(jié)點(diǎn)的二叉樹的中序遍歷為，其中數(shù)字為節(jié)點(diǎn)編號。若某個(gè)子樹為空，規(guī)定其加分為，葉子的加分就是葉節(jié)點(diǎn)本身的分?jǐn)?shù)。試求一棵符合中序遍歷為且加分最高的二叉樹。 動態(tài)規(guī)劃練習(xí)題-總 題目描述設(shè)一個(gè)n個(gè)節(jié)點(diǎn)的二叉樹tree的中序遍歷為（1,2,3,…,n），其中數(shù)字1,2,3,…,n為節(jié)點(diǎn)編號。每個(gè)節(jié)點(diǎn)都有一個(gè)分?jǐn)?shù)（均為正整數(shù)），記第i個(gè)節(jié)點(diǎn)的分?jǐn)?shù)為di，tree及...

    Miracle 評論0 收藏0

  • 第7期 Datawhale 組隊(duì)學(xué)習(xí)計(jì)劃

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

    dinfer 評論0 收藏0

發(fā)表評論

0條評論

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