P6 爬楼梯 LeetCode70

P6 爬楼梯，难度简单，主要标签为动态规划。

题目

English

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

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

Note: Given n will be a positive integer.

Example 1:

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

Input: 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

中文

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

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

注意：给定 n 是一个正整数。

示例 1：

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

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

LeetCode题目链接https://leetcode-cn.com/problems/climbing-stairs/

---

解题思路

20191209记录

递归

# Python代码实现
class Solution:
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1:
            return 1
        elif n == 2:
            return 2
        else:
            return self.climbStairs(n - 1) + self.climbStairs(n - 2)

直接递归会超时，存在大量重复计算。

动态规划

// java代码实现
class Solution {
    public int climbStairs(int n) {
        int[] a = new int[100];
        a[0] = 1;
        a[1] = 2;
        for(int i = 2; i <= n-1; i++) {
            a[i] = a[i - 1] + a[i - 2];
        }
	    return a[n - 1];
    }
}

本文作者： Yao Zhu
发布时间： 2019-12-09
最后更新： 2019-12-09
本文链接： https://juoyo.github.io/posts/37233cc0.html
版权声明： 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！

赏

谢谢你请我吃糖果

支付宝

微信