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

資訊專欄INFORMATION COLUMN

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

enali / 1430人閱讀

摘要：程序?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級(jí)，剛開始時(shí)你在第一級(jí)，若每次只能跨上一級(jí)或二級(jí)，要走上第M級(jí)，共有多少種走法？

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

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

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

假設(shè)10級(jí)，考慮只差最后一步到10級(jí)，一步走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] 拆開的階，這樣往下，分階段將問題簡(jiǎn)化。

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

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

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

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

首先用遞歸進(jìn)行實(shí)現(xiàn)，與動(dòng)態(tài)規(guī)劃做比較。前者代碼簡(jiǎn)潔，但執(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）動(dòng)態(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
每次迭代，只保留之前的兩個(gè)狀態(tài)，即可推導(dǎo)新的狀態(tài)。

源程序：

import java.util.Scanner;

/**
 * Input:輸入數(shù)據(jù)首先包含一個(gè)整數(shù)N，表示測(cè)試實(shí)例的個(gè)數(shù)，然后是N行數(shù)據(jù)，每行包含一個(gè)整數(shù)M（1<=M<=40）,表示樓梯的級(jí)數(shù)。
 * Output:對(duì)于每個(gè)測(cè)試實(shí)例，請(qǐng)輸出不同走法的數(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、算法分析

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

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/73906.html

相關(guān)文章

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

    摘要：動(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)移方程我們來看一到題目題目有一座高度是級(jí)臺(tái)階的樓梯，從下往上走，每跨一步只能向上級(jí)或者級(jí)臺(tái)階。 概念 動(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)...

    cyixlq 評(píng)論0 收藏0

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

    摘要：程序員小吳打算使用動(dòng)畫的形式來幫助理解遞歸，然后通過遞歸的概念延伸至理解動(dòng)態(tài)規(guī)劃算法思想。因此，分治策略一般用來解決子問題相互對(duì)立的問題，稱為標(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)概念（繞來繞去）的往往是相對(duì)比較難以理解的兩個(gè)抽象知識(shí)點(diǎn)。...

    cnio 評(píng)論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ù)的增長(zhǎng)。 Time：2019/4/12Title:Clibing SrairsDifficulty: EasyAuthor:小鹿 題目：Climbing Stairs You a...

    chemzqm 評(píng)論0 收藏0

  • 70-爬樓梯

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

    CompileYouth 評(píng)論0 收藏0

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

    摘要：代碼思路最簡(jiǎn)單的一維動(dòng)態(tài)規(guī)劃問題，自底向上。上代碼看效果，時(shí)間復(fù)雜度線性級(jí)別這里有一個(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 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

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