Day16 Leetcode Array系列---- Climbing Stairs

本次題目 Climbing Stairs by JS

這題是要爬樓梯，題目給予樓梯的階梯數，我們可以選擇一次跨 1 步或跨 2 步，希望可以知道有幾種上樓的方法

input1 = 2
output1 = 2
// 1. 1 step + 1 step
// 2. 2 steps

input2 =  3
output2 = 3
// 1. 1 step + 1 step + 1 step
// 2. 1 step + 2 steps
// 3. 2 steps + 1 step

思考路線

1. 先列舉不同層數的樓梯的走法
2. 歸納他們的特性

Coding Time

我先列舉 1~5 層樓梯的走法

1 層 --- 1 種走法
1

2 層 --- 2 種走法
2
1 1

3 層 --- 3 種走法
2 1
1 2
1 1 1

4 層 --- 5 種走法
2 2
1 1 2
1 2 1
2 1 1 
1 1 1 1 

5 層 --- 8 種走法
2 2 1
2 1 2
1 2 2 
1 1 1 2
1 1 2 1
1 2 1 1 
2 1 1 1
1 1 1 1 1

仔細一看這個就是兔子數列啊

就依照兔子數列的規則去設計

除了前 2 天是 1 (index 0 1)，其餘天數的兔子數量皆是前 2 天的和，這與爬樓梯這題相似，除了 2 層以下的階梯，每多 1 階梯走法就會是前 2 層走法的和

function climbing(num){
    a = []
    for(let i =0; i <= num; i++){
        if( a.length < 2){
            a[i] = 1
        }else{
            a[i] = a[i-1] +a[i-2]
        }
        
    }
    return a[num]
}

function expect(a,b){
    console.log(a == b)
}


expect(climbing(input1),output1)
expect(climbing(input2),output2)

解題前要先找出觀察或是找出數學規律，如果沒有列出５層走法，我無法確認它是兔子數學，窮舉找規律有時候還是有用的

今天到此為止，有任何問題請在下方留言或透過email、GitHub聯絡我，感謝閱讀

Daily kitty