動態規劃-樓梯問題

enali 發布于2019-08-16 16:07 / 1369人閱讀

摘要：程序實現首先用遞歸進行實現，與動態規劃做比較。遞歸動態規劃從底到上推導，，每次迭代，只保留之前的兩個狀態，即可推導新的狀態。

1、問題描述

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

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

Sample Input
2
2
3
Sample Output
1
2

2、思路分析

利用動態規劃（DP，dynamic programming）思想，簡單來說：大事化小小事化了

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

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

得到三個動態規劃的概念：
【最優子結構】：F(9)和F(8)，是F(10)的最優子結構
【邊界】：F(1)和F(2)是問題的邊界，無法再簡化/拆解
【狀態轉移方程】：F(10)=F(9)+F(8)，上下階段的關系

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

3、程序實現

首先用遞歸進行實現，與動態規劃做比較。前者代碼簡潔，但執行效率不如后者。

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）動態規劃

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

源程序：

import java.util.Scanner;

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

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

云服務器 GPU云服務器動態規劃動態規劃python java動態規劃代碼 java零錢動態規劃

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

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

動態規劃入門（以爬樓梯為例）

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

cyixlq 2019-08-23 10:52 評論0 收藏0
看動畫輕松理解「遞歸」與「動態規劃」

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

cnio 2019-07-30 18:41 評論0 收藏0
LeetCode 之 JavaScript 解答第70題 —— 爬樓梯（Climbing Stair

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

chemzqm 2019-08-23 16:55 評論0 收藏0
70-爬樓梯

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

CompileYouth 2019-08-19 11:05 評論0 收藏0
每日一道算法題--leetcode 746--使用最小花費爬樓梯--python

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

Euphoria 2019-05-27 17:41 評論0 收藏0