動態規劃算法的思想及實現

includecmath 發布于2019-08-20 14:01 / 2309人閱讀

摘要：介紹動態規劃簡稱是算法設計思想當中最難也是最有趣的部分了，動態規劃適用于有重疊子問題和最優子結構性質的問題，是一種在數學計算機科學和經濟學中經常使用的，通過把原問題分解為相對簡單的子問題的方式求解復雜問題的方法。

介紹

動態規劃(簡稱DP)是算法設計思想當中最難也是最有趣的部分了，動態規劃適用于有重疊子問題和最優子結構性質的問題，是一種在數學、計算機科學和經濟學中經常使用的，通過把原問題分解為相對簡單的子問題的方式求解復雜問題的方法。使用動態規劃方法解題有較高的時間效率，關鍵在于它減少了很多不必要的計算和重復計算的部分

它的思想就是把一個大的問題進行拆分，細分成一個個小的子問題，且能夠從這些小的子問題的解當中推導出原問題的解。同時還需要滿足以下兩個重要性質才能進行動態規劃

最優子結構性: 既所拆分的子問題的解是最優解。

子問題重疊性質: 既在求解的過程當中，每次產生的子問題并不總是新問題，有些子問題會被重復計算多次。動態規劃算法正是利用了這種子問題的重疊性質，對每一個子問題只計算一次，然后將其計算結果保存在一個表格中，當再次需要計算已經計算過的子問題時，只是在表格中簡單地查看一下結果，從而獲得較高的解題效率

舉個栗子

首先先引一道動態規劃的經典問題最長不下降子序列

它的定義是: 設有由n個不相同的整數組成的數列b[n],若有下標$i_1

例如

13,7,9,16,38,24,37,18,44,19,21,22,63,15

那么就有13<16<38<44<63長度為5的不下降子序列。
但是經過觀察實際上還有7<9<16<18<19<21<22<63長度為8的不下降子序列，那么是否還有更長的不下降子序列呢？請找出最長的不下降子序列

輸入格式

第一行為n，表示n個數(n<=100000),第二行為n個數的數值(數字之間用空格隔開且最后一個數字末尾不能留有空格)

輸出格式

一個整數，表示最長不下降子序列的長度。

輸入例子

1 3 1 2

輸出例子

思路

假如要求得某一段的最優，就要想更小段的最優怎么求，再看看由最小段的最優能否擴大推廣到最大段的最優;

假設這么一個表:

第三行表示該序列元素的所能連接的最長不下降子序列的長度，因為本身長度為1，所以初始值都為1

第四行表示鏈接于哪個序列元素形成最長不下降子序列

先從倒數第二項63算起，在它的后面僅有一項，因此僅作一次比較，因為63>15，所以從63出發，不作任何鏈接，長度還是為1。

再看倒數第三項22，在它的后面有2項，因此必須要在這2項當中找出比22大，長度又是最長的數值作為鏈接，由于只有22<63,所以修改22的長度為2，即自身長度加上所鏈接數值的長度，并修改鏈接位置為13，也就是63的下標。

再看倒數第四項21，在它的后面有3項，因此必須要在這3項當中找出比21大，長度又是最長的數值作為鏈接(注意:是長度)，很容易看出，數值22滿足該條件，因此，修改21的長度為3，并修改鏈接位置為12，即22的序列下標。

依次類推，最后結果如下表:

最終狀態的轉移方程式為: $f(i) = max {f(j)} +1 (b_j

代碼

process.stdin.setEncoding("utf8");

var arr = [];
var bool = 0;
var n = 0;
var longest = 1;
var a = [];
var dp = [];

process.stdin.on("readable", function() {
  var chunk = process.stdin.read();
  if (chunk !== null) {
      arr.push(chunk.trim())
  }

  if(bool>=2){
      n = arr[0];
      process.stdin.emit("end")
  }

  bool++

});


process.stdin.on("end", function() {

    a = arr.slice(1).join(" ").split(" ").map(function(index, elem) {
        return parseInt(index);
    })

    for(let i = 0;ia[j]){
                dp[i] = Math.max(dp[j]+1,dp[i])
            }
            longest = Math.max(dp[i],longest)
        }

    }

    console.log("最長長度為:"+longest);


      process.stdout.write("end");
});

云服務器 GPU云服務器最優合并問題的算法思想最短路徑算法思想動態規劃動態html的實現

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/81370.html

基本算法思想：遞歸+分治+動態規劃+貪心+回溯+分支限界

摘要：代碼實現見下面評論對應代碼動態規劃基本思想和分治法基本思想有共同的地方，不同的是子問題往往不是獨立的，有事母問題要借助子問題的解來判斷，因此把已經計算好的問題記錄在表格中，后續如果需要查詢一下，可以避免重復計算，這是動態規劃的基本思想。作者：心葉時間：2018-05-01 19:28 本文對應github地址：https://github.com/yelloxing/... 以上實現...

EscapedDog 2019-08-26 11:52 評論0 收藏0
前端跳槽面試算法——動態規劃

摘要：我記得大三參加騰訊的校招面試時只準備了幾種常見的排序算法就足以應對了，然而今年包括今日頭條在內的多家大廠的前端筆試題目中都出現了貪心算法動態規劃分治算法等進階性的算法題目。本篇博客參考今日頭條銀國徽老師的《js版數據結構與算法》Part1改編自《漫畫算法》原作者：程序員小灰前言眾所周知，與后臺開發人員相比，算法是我們前端開發人員的一個弱項。而近兩年隨著互聯網行業競爭愈發激烈，市場上對前端崗位...

mushang 2019-05-21 19:07 評論0 收藏0
從斐波那契數列看遞歸和動態規劃

摘要：大名鼎鼎的斐波那契數列，，，，，，，，使用數學歸納法可以看出其規律為。對于斐波那契數列的求解，有自頂向下的記憶化搜索遞歸和自下向上的迭代法，他們都使用了動態規劃的思想。大名鼎鼎的斐波那契數列：0，1，1，2，3，5，8，13，21...使用數學歸納法可以看出其規律為：f(n) = f(n-1) + f(n-2)。遞歸下面首先直接使用遞歸（JavaScript實現）來求解第 n ...

charles_paul 2019-08-22 18:30 評論0 收藏0
動態規劃入門（以爬樓梯為例）

摘要：動態規劃算法通常基于一個遞推公式及一個或多個初始狀態。動態規劃有三個核心元素最優子結構邊界狀態轉移方程我們來看一到題目題目有一座高度是級臺階的樓梯，從下往上走，每跨一步只能向上級或者級臺階。概念動態規劃(dynamic programming)是運籌學的一個分支，是求解決策過程(decision process)最優化的數學方法。動態規劃算法通常基于一個遞推公式及一個或多個初始狀態...

cyixlq 2019-08-23 10:52 評論0 收藏0