算法-- 爬楼梯(Kotlin)

题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶


示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
 1 阶 + 1 阶 + 1 阶
 1 阶 + 2 阶
 2 阶 + 1 阶
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

提示：

1 <= n <= 45

https://leetcode.cn/problems/climbing-stairs/

解决思路

1. 本问题其实常规解法可以分成多个子问题，爬第n阶楼梯的方法数量，等于 2 部分之和
   爬上 n-1阶楼梯的方法数量。因为再爬1阶就能到第n阶
   爬上 n-2阶楼梯的方法数量，因为再爬2阶就能到第n阶
   所以我们得到公式 dp[n] = dp[n-1] + dp[n-2]
   同时需要初始化 dp[0]=1 和 dp[1]=1d
   时间复杂度：O(n)

2.既然 dp[n] = dp[n-1] + dp[n-2]
那么我们可以用滑动数组去解决

解决方法

    fun climbStairs(n: Int): Int {

        val intArray = IntArray(n + 1)
        intArray[0] = 1
        intArray[1] = 1
        for (i in 2..n) {
            intArray[i] = intArray[i - 1] + intArray[i - 2]
        }
        return intArray[n]
    }
1
2
3
4
5
6
7
8
9
10

    fun climbStairs2(n: Int): Int {
        var q = 1
        var p = 1
        var result = 1
        for (i in 2..n) {
            result = q + p
            q = p
            p = result
        }
        return result
    }
1
2
3
4
5
6
7
8
9
10
11

总结

1.这个题一下没有想出来怎么做
看了一下题解才做出来