成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

動(dòng)態(tài)規(guī)劃入門（以爬樓梯為例）

cyixlq / 946人閱讀

摘要：動(dòng)態(tài)規(guī)劃算法通?；谝粋€(gè)遞推公式及一個(gè)或多個(gè)初始狀態(tài)。動(dòng)態(tài)規(guī)劃有三個(gè)核心元素最優(yōu)子結(jié)構(gòu)邊界狀態(tài)轉(zhuǎn)移方程我們來看一到題目題目有一座高度是級臺階的樓梯，從下往上走，每跨一步只能向上級或者級臺階。

概念

動(dòng)態(tài)規(guī)劃(dynamic programming)是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過程(decision process)最優(yōu)化的數(shù)學(xué)方法。
動(dòng)態(tài)規(guī)劃算法通?；谝粋€(gè)遞推公式及一個(gè)或多個(gè)初始狀態(tài)。 當(dāng)前子問題的解將由上一次子問題的解推出。

基本思想

要解決一個(gè)給定的問題，我們需要解決其不同部分（即解決子問題），再合并子問題的解以得出原問題的解。
通常許多子問題非常相似，為此動(dòng)態(tài)規(guī)劃法試圖只解決每個(gè)子問題一次，從而減少計(jì)算量。
一旦某個(gè)給定子問題的解已經(jīng)算出，則將其記憶化存儲，以便下次需要同一個(gè)子問題解之時(shí)直接查表。
這種做法在重復(fù)子問題的數(shù)目關(guān)于輸入的規(guī)模呈指數(shù)增長時(shí)特別有用。
動(dòng)態(tài)規(guī)劃有三個(gè)核心元素：
1.最優(yōu)子結(jié)構(gòu)
2.邊界
3.狀態(tài)轉(zhuǎn)移方程

我們來看一到題目

題目 
有一座高度是10級臺階的樓梯，從下往上走，每跨一步只能向上1級或者2級臺階。求出一共有多少種走法。

比如，每次走1級臺階，一共走10步，這是其中一種走法。
再比如，每次走2級臺階，一共走5步，這是另一種走法。

但是這樣一個(gè)個(gè)算太麻煩了，我們可以只去思考最后一步怎么走，如下圖

這樣走到第十個(gè)樓梯的走法 = 走到第八個(gè)樓梯 + 走到第九個(gè)樓梯
我們用f(n)來表示 走到第n個(gè)樓梯的走法，所以就有了f(10) = f(9) + f(8)
然后f(9) = f(8) + f(7), f(8) = f(7) + f(6)......

這樣我們就得出來一個(gè)遞歸式：
f(n) = f(n-1) + f(n-2);
還有兩個(gè)初始狀態(tài)：
f(1) = 1;
f(2) = 2;

這樣就得出了第一種解法

方法一：遞歸求解 
function getWays(n) {

    if (n < 1) return 0;
    if (n == 1) return 1;
    if (n == 2) return 2;

    return getWays(n-1) + getWays(n-2); 
}

這種方法的時(shí)間復(fù)雜度為O(2^n)

可以看到這是一顆二叉樹，數(shù)的節(jié)點(diǎn)個(gè)數(shù)就是我們遞歸方程需要計(jì)算的次數(shù)，
數(shù)的高度為N，節(jié)點(diǎn)個(gè)數(shù)近似于2^n
所以時(shí)間復(fù)雜度近似于O(2^n)

但是這種方法能不能優(yōu)化呢？
我們會發(fā)現(xiàn)有些值被重復(fù)計(jì)算，如下圖

相同顏色代表著重復(fù)的部分，那么我們可不可以把這些重復(fù)計(jì)算的值記錄下來呢？
這樣的優(yōu)化就有了第二種方法

方法二：備忘錄算法 
const map = new Map(); 
function getWays(n) {

    if (n < 1) return 0;
    if (n == 1) return 1;
    if (n == 2) return 2;

    if (map.has(n)) {
        return map.get(n);
    }
    const value = getWays(n-1) + getWays(n-2);
    map.set(n, value);
    return value; 
}

因?yàn)閙ap里最終會存放n-2個(gè)鍵值對，所以空間復(fù)雜度為O(n),時(shí)間復(fù)雜度也為O(n)

繼續(xù)想一想這就是最優(yōu)的解決方案了嗎？

我們回到一開始的思路，我們是假定前面的樓梯已經(jīng)走完，只考慮最后一步，所以才得出來f(n) = f(n-1) + f(n-2)的遞歸式，這是一個(gè)置頂向下求解的式子
一般來說，按照正常的思路應(yīng)該是一步一步往上走，應(yīng)該是自底向上去求解才比較符合正常人的思維，我們來看看行不行的通


這是一開始走的一個(gè)和兩個(gè)樓梯的走法數(shù),即之前說的初始狀態(tài)


這是進(jìn)行了一次迭代得出了3個(gè)樓梯的走法，f(3)只依賴于f(1) 和 f(2)

繼續(xù)看下一步

這里又進(jìn)行了一次迭代得出了4個(gè)樓梯的走法，f(4)只依賴于f(2) 和 f(3)

我們發(fā)現(xiàn)每次迭代只需要前兩次迭代的數(shù)據(jù)，不用像備忘錄一樣去保存所有子狀態(tài)的數(shù)據(jù)

方法三：動(dòng)態(tài)規(guī)劃求解 
function getWays(n) {

    if (n < 1) return 0;
    if (n == 1) return 1;
    if (n == 2) return 2;

    // a保存倒數(shù)第二個(gè)子狀態(tài)數(shù)據(jù)，b保存倒數(shù)第一個(gè)子狀態(tài)數(shù)據(jù)， temp 保存當(dāng)前狀態(tài)的數(shù)據(jù)
    let a = 1, b = 2;
    let temp = a + b;
    for (let i = 3; i <= n; i++) {
        temp = a + b;
        a = b;
        b = temp; 
    }
    return temp; 
}

這是我們可以再看看當(dāng)前的時(shí)間復(fù)雜度和空間復(fù)雜度
當(dāng)前時(shí)間復(fù)雜度仍為O(n)，但空間復(fù)雜度降為O(1)
這就是理想的結(jié)果

總結(jié)

這只是動(dòng)態(tài)規(guī)劃里最簡單的題目之一，因?yàn)樗挥幸粋€(gè)變化維度
當(dāng)變化維度變成兩個(gè)、三個(gè)甚至更多時(shí)，會更加復(fù)雜，背包問題就是比較典型的多維度問題，有興趣的可以去網(wǎng)上看看《背包九講》

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

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/96772.html

相關(guān)文章

  • 看動(dòng)畫輕松理解「遞歸」與「動(dòng)態(tài)規(guī)劃」

    摘要：程序員小吳打算使用動(dòng)畫的形式來幫助理解遞歸，然后通過遞歸的概念延伸至理解動(dòng)態(tài)規(guī)劃算法思想。因此，分治策略一般用來解決子問題相互對立的問題，稱為標(biāo)準(zhǔn)分治，而動(dòng)態(tài)規(guī)劃用來解決子問題重疊的問題。難點(diǎn)就在于找出動(dòng)態(tài)規(guī)劃中的這三個(gè)概念。 在學(xué)習(xí)「數(shù)據(jù)結(jié)構(gòu)和算法」的過程中，因?yàn)槿肆?xí)慣了平鋪直敘的思維方式，所以「遞歸」與「動(dòng)態(tài)規(guī)劃」這種帶循環(huán)概念（繞來繞去）的往往是相對比較難以理解的兩個(gè)抽象知識點(diǎn)。...

    cnio 評論0 收藏0

  • 動(dòng)態(tài)規(guī)劃-樓梯問題

    摘要：程序?qū)崿F(xiàn)首先用遞歸進(jìn)行實(shí)現(xiàn)，與動(dòng)態(tài)規(guī)劃做比較。遞歸動(dòng)態(tài)規(guī)劃從底到上推導(dǎo)，，每次迭代，只保留之前的兩個(gè)狀態(tài)，即可推導(dǎo)新的狀態(tài)。 1、問題描述 有一樓梯共M級，剛開始時(shí)你在第一級，若每次只能跨上一級或二級，要走上第M級，共有多少種走法？ 輸入輸出描述Input輸入數(shù)據(jù)首先包含一個(gè)整數(shù)N，表示測試實(shí)例的個(gè)數(shù)，然后是N行數(shù)據(jù)，每行包含一個(gè)整數(shù)M（1

    enali 評論0 收藏0

  • LeetCode 之 JavaScript 解答第70題 —— 爬樓梯（Climbing Stair

    摘要：小鹿題目假設(shè)你正在爬樓梯。需要階你才能到達(dá)樓頂。你有多少種不同的方法可以爬到樓頂呢注意給定是一個(gè)正整數(shù)。算法思路二種解決思路，第一利用遞歸第二利用動(dòng)態(tài)規(guī)劃。就是因?yàn)橛辛酥貜?fù)元素的計(jì)算，導(dǎo)致了時(shí)間復(fù)雜度成指數(shù)的增長。 Time：2019/4/12Title:Clibing SrairsDifficulty: EasyAuthor:小鹿 題目：Climbing Stairs You a...

    chemzqm 評論0 收藏0

  • 70-爬樓梯

    摘要：前言最近在練習(xí)動(dòng)態(tài)規(guī)劃的題目，然后就隨便選擇了一道簡單的題目爬樓梯，題目如下假設(shè)你正在爬樓梯。斐波那契數(shù)列爬樓梯實(shí)現(xiàn)代碼爬樓梯 前言 最近在練習(xí)動(dòng)態(tài)規(guī)劃的題目，然后就隨便選擇了一道簡單的題目——爬樓梯，題目如下： 假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。每次你可以爬 1 或 2 個(gè)臺階。你有多少種不同的方法可以爬到樓頂呢？注意：給定 n 是一個(gè)正整數(shù)。 示例 1： 輸入： 2 ...

    CompileYouth 評論0 收藏0

  • 每日一道算法題--leetcode 746--使用最小花費(fèi)爬樓梯--python

    摘要：代碼思路最簡單的一維動(dòng)態(tài)規(guī)劃問題，自底向上。上代碼看效果，時(shí)間復(fù)雜度線性級別這里有一個(gè)動(dòng)態(tài)規(guī)劃系列題目整理，供大家參考【題目描述】 showImg(https://user-gold-cdn.xitu.io/2019/5/27/16af88f6f38f5da3); ??！題干里的示例1需要仔細(xì)看一下哦，要到達(dá)頂層，即20那一層，可以跳過20這一層達(dá)到更高一層，也因此我們給cost數(shù)組最后加一個(gè)...

    Euphoria 評論0 收藏0

發(fā)表評論

0條評論

最新活動(dòng)
閱讀需要支付1元查看
<