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

資訊專欄INFORMATION COLUMN

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

enali / 1377人閱讀

摘要：程序?qū)崿F(xiàn)首先用遞歸進(jìn)行實現(xiàn)，與動態(tài)規(guī)劃做比較。遞歸動態(tài)規(guī)劃從底到上推導(dǎo)，，每次迭代，只保留之前的兩個狀態(tài)，即可推導(dǎo)新的狀態(tài)。

1、問題描述

有一樓梯共M級，剛開始時你在第一級，若每次只能跨上一級或二級，要走上第M級，共有多少種走法？

輸入輸出描述
Input
輸入數(shù)據(jù)首先包含一個整數(shù)N，表示測試實例的個數(shù)，然后是N行數(shù)據(jù)，每行包含一個整數(shù)M（1<=M<=40）,表示樓梯的級數(shù)。
Output
對于每個測試實例，請輸出不同走法的數(shù)量
示例：

Sample Input
2
2
3
Sample Output
1
2
2、思路分析

利用動態(tài)規(guī)劃（DP，dynamic programming）思想，簡單來說：大事化小小事化了

假設(shè)10級，考慮只差最后一步到10級，一步走1階或2階，只有兩種可能：到9階和到8階。
如果到9階的走法有X種，到8階的走法有Y種，那么，總走法=X+Y。
即：F(10)=F(9)+F(8)
同理，F(xiàn)(9)=F(8)+F(7)，F(xiàn)(8)=F(7)+F(6)，這樣問題可以從10階到 [9和8] 階，再到 [9和8] 拆開的階，這樣往下，分階段將問題簡化。

尋找基準(zhǔn)或者初始解：當(dāng)為F(2)和F(1)時，前者有兩種走法（1+1，2），后者有一種走法（1）。
即：①F(2)=2，F(xiàn)(1)=1。再加上②F(10)=F(9)+F(8)，

得到三個動態(tài)規(guī)劃的概念：
【最優(yōu)子結(jié)構(gòu)】：F(9)和F(8)，是F(10)的最優(yōu)子結(jié)構(gòu)
【邊界】：F(1)和F(2)是問題的邊界，無法再簡化/拆解
【狀態(tài)轉(zhuǎn)移方程】：F(10)=F(9)+F(8)，上下階段的關(guān)系

遞歸公式：F(n)=F(n-1)+F(n-2)，實為斐波那契數(shù)列的遞歸公式。

3、程序?qū)崿F(xiàn)

首先用遞歸進(jìn)行實現(xiàn)，與動態(tài)規(guī)劃做比較。前者代碼簡潔，但執(zhí)行效率不如后者。

1）遞歸 
int getWays(int n){
    if(n<1) return 0;
    if(n==1) return 1;
    if(n==2) return 2;
    return getWays(n-1)+getWays(n-2)
}
2）動態(tài)規(guī)劃

從底到上推導(dǎo)：
F(1)=1，F(xiàn)(2)=2，
F(3)=F(2)+F(1)=1+2
F(4)=F(3)+F(2)=3+2
每次迭代，只保留之前的兩個狀態(tài)，即可推導(dǎo)新的狀態(tài)。

源程序：

import java.util.Scanner;

/**
 * Input:輸入數(shù)據(jù)首先包含一個整數(shù)N，表示測試實例的個數(shù)，然后是N行數(shù)據(jù)，每行包含一個整數(shù)M（1<=M<=40）,表示樓梯的級數(shù)。
 * Output:對于每個測試實例，請輸出不同走法的數(shù)量
 */
public class DPSumsung {

    public static int getWays(int n) {
        if(n<1) return 0;
        if(n==1) return 1;
        if(n==2) return 2;
        
        int a=1;
        int b=2;
        int next=0;
        for(int i=3;i<=n;i++) {
            next=a+b;
            a=b;
            b=next;
        }
        return next;
    }
    
    public static void main(String[] args) {

        Scanner sc=new Scanner(System.in);
        int count=sc.nextInt();
        int[] ways=new int[count];
        int i=0;
        int n=sc.nextInt();
        while(n>=1&&n<=40) {         
            ways[i++]=DPSumsung.getWays(n);
            if(i>=count)
                break;
            n=sc.nextInt();
        }
        for(int temp:ways) {
            System.out.println(temp);
        }
        sc.close();
    }
}
4、算法分析

時間復(fù)雜度為O(N)，空間復(fù)雜度為O(1)。

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

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

相關(guān)文章

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

    摘要：動態(tài)規(guī)劃算法通?；谝粋€遞推公式及一個或多個初始狀態(tài)。動態(tài)規(guī)劃有三個核心元素最優(yōu)子結(jié)構(gòu)邊界狀態(tài)轉(zhuǎn)移方程我們來看一到題目題目有一座高度是級臺階的樓梯，從下往上走，每跨一步只能向上級或者級臺階。 概念 動態(tài)規(guī)劃(dynamic programming)是運籌學(xué)的一個分支，是求解決策過程(decision process)最優(yōu)化的數(shù)學(xué)方法。動態(tài)規(guī)劃算法通?；谝粋€遞推公式及一個或多個初始狀態(tài)...

    cyixlq 評論0 收藏0

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

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

    cnio 評論0 收藏0

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

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

    chemzqm 評論0 收藏0

  • 70-爬樓梯

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

    CompileYouth 評論0 收藏0

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

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

    Euphoria 評論0 收藏0

發(fā)表評論

0條評論

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