iT邦幫忙

2024 iThome 鐵人賽

DAY 6
0

原文題目

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

題目摘要

  1. 給定一個樓梯,共有 n 階。
  2. 每次可以選擇爬 1 階或 2 階,問共有多少種不同的方式爬到樓梯頂端。

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

解題思路

  1. 問題拆解
    • 假設你現在在第 n 階,之前一步可能從 n-1 階爬上來,也可能是從 n-2 階爬上來。這意味著你到達第 n 階的方式總數等於你到達 n-1 階的方式總數加上你到達 n-2 階的方式總數。
    • 因此,問題可以拆分成一個遞迴的關係:f(n) = f(n-1) + f(n-2),這跟斐波那契數列的定義是一樣的。
  2. 基礎情況
    • 當你只有一階時,只有一種方式,就是直接爬一階。
    • 當你有兩階時,則有兩種方式,分別是:一次爬兩階或分兩次各爬一階。
  3. 總結
    • 計算每一階的方式數,逐步累加即可,直到到達第 n 階。
    • 可以使用遞迴或動態規劃來實現,但動態規劃能夠更有效地解決這類問題,因為它避免了重複計算。

程式碼

class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n+1];
        //基礎情況:當今天n<3時,output都會恰好等於n
        if(n<3){
            return n;
        }
        //計算dp[3]前需要先宣告dp[1]、dp[2]
        dp[1]=1;
        dp[2]=2;
        //n>2以後只須根據前兩個加總即可算出所有步數可能
        for(int i=3; i<n+1; i++){
            dp[i]=dp[i-2]+dp[i-1];
        }
        return dp[n];
    }
}

結論: 爬樓梯問題是一個很好的練習動態規劃的範例,它告訴我們如何把複雜的問題拆解成簡單的子問題,進而找到解決方案。實際上,這個問題和斐波那契數列有很多相似之處,因為每一步的選擇都取決於前面兩步的結果。生活中,我們也常面對需要分步完成的任務,這種問題就像是提前計劃每一步,讓我們能夠更有效率地達成目標。掌握了這種思路,不僅能在程式設計中受益,也能在日常生活的規劃和決策中發揮作用。


上一篇
Day5 演算法介紹:動態規劃(Dynamic Programming)
下一篇
Day7 Dynamic Programming 題目2:198. House Robber
系列文
Java刷題B:Leetcode Top 100 Liked30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言