Leetcode70-爬楼梯

• 题目要求：

• 思路 1：

  • 定义数组 num，长度为给定的 n 的长度
  • 如果 n 大于 1，num[0] 赋为 1，因为走上第一个台阶只有一种方法，也就是迈一步
  • 如果 n 大于 2，num[1] 赋为 2，也就是走上第二个台阶有两种方法，第一种是走一步，再走一步，第二种是直接走两步
  • 然后 for 循环遍历数组，从下标位置为 2 开始遍历，也就是上第三个台阶，可以是第二个台阶走一步，也可以是从第一个台阶走一步上来，那么第三个台阶的方法就是第二个台阶的方法加上第一个台阶的方法，也就是 num[i] 的台阶的方法数为 num[i-1] 与 num[i-2] 的和。
  • 最后返回数组最后一位元素的值即可
• 核心代码：

# 初始化数组，可以为 0，可以为 None
num = [0] * n
# 如果 n 大于等于 1，那么走第一个台阶的方法有一个，就是走一步
if n >= 1:
    num[0] = 1
    # 如果台阶数大于等于 2，走第二个台阶的方法有两种
    if n >= 2:
        num[1] = 2
        # 第二个台阶之后的台阶就可以通过这个台阶的前两个台阶的方法数的和求来
        for i in range(2,n):
            num[i] = num[i-1] + num[i-2]
# 返回结果
return num[-1]

• 完整代码：

class Solution:
    def climbStairs(self, n: int) -> int:
        num = [0] * n
        if n >= 1:
            num[0] = 1
            if n >= 2:
                num[1] = 2
                for i in range(2,n):
                    num[i] = num[i-1] + num[i-2]
        return num[-1]

• 思路 2：

  • 对比思路 1，其实到台阶 n，只有台阶 n - 1 和 n - 2 的方法数是需要知道的，之前保存的所有数值都是不重要的
  • 所以维护一个 pre，用来保存走前一个的前一个台阶的方法数，初始值赋为 0
  • 维护一个 cur，用来保存走当前台阶的前一个台阶的方法数，初始值为 1
  • for 循环遍历，遍历到当前的台阶的方法数为 pre+cur，在这之前，要先把 pre 赋给 cur，python 有一个特性就是两个变量可以直接进行交换，具体见代码
• 核心代码：

pre , cur = 0 , 1
for i in range(n):
    pre , cur = cur , pre + cur
return cur

• 完整代码：

class Solution:
    def climbStairs(self, n: int) -> int:
        pre , cur = 0 , 1
        for i in range(n):
            pre , cur = cur , pre + cur
        return cur