【LeetCode】【Kotlin】70. Climbing Stairs (Fibonacci number)

題意

有n階樓梯，每次可以走1或2階，有幾種走完的方式?

解題方式

• 若階梯只有一階，則只有一種方式
• 若階梯有兩階，則有1+1與2兩種方式
• 若階梯有三階或以上，則若踏上最後一階時是走一階，則除卻最後一次，前面有n-1階，如同n-1階時有相同種方式；若踏上最後一階時是走二階，則除卻最後一次，前面有n-2階，如同n-2階時有相同種方式。

方法一 : 使用遞迴方式

會超時

class Solution {
    fun climbStairs(n: Int): Int {
        return when{
            n<=2 -> return n
            else -> return climbStairs(n-1) + climbStairs(n-2)
        }
    }
}

方法二: 使用 for 迴圈

class Solution {
    fun climbStairs(n: Int): Int {
        if(n<=2) return n

        var nMinus1Steps = 1
        var nSteps = 2

        for (i in 3..n){
            var tempSteps = nMinus1Steps + nSteps
            nMinus1Steps = nSteps
            nSteps = tempSteps
        }

        return nSteps
    }
}

126ms / 32.5MB (beats 53.71% / 86.39%)