【Leetcode】70. 爬楼梯

raoyi 发布于2019-07-24 10:49 / 1473人阅读

摘要：题目假设你正在爬楼梯。需要阶你才能到达楼顶。你有多少种不同的方法可以爬到楼顶呢注意给定是一个正整数。示例输入输出解释有两种方法可以爬到楼顶。阶阶阶阶阶阶阶题解这个题目只要模拟一下基本就能想到是，状态方程写出来就是斐波那契数列。

题目

假设你正在爬楼梯。需要 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 阶

题解

这个题目只要模拟一下基本就能想到是TP，状态方程写出来就是斐波那契数列。
dp[i] = dp[i-1] + dp[i-2]
i-1的时候跳一步可以到达i
i-2的时候跳一步是i-1，这个变成dp[i-1]的子问题了,直接跳两步可以到达i

java

class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

python

class Solution:
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [1 for i in range(n + 1)]
        for i in range(2, n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]

热门文章

【Spring】IOC是啥有什么好处

【Leetcode】67. 二进制求和

【Leetcode】66. 加一

GPU云服务器云服务器爬楼梯 LeetCode 楼梯 LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/35970.html

【Leetcode】70. 爬楼梯

摘要：题目假设你正在爬楼梯。需要阶你才能到达楼顶。你有多少种不同的方法可以爬到楼顶呢注意给定是一个正整数。示例输入输出解释有两种方法可以爬到楼顶。阶阶阶阶阶阶阶题解这个题目只要模拟一下基本就能想到是，状态方程写出来就是斐波那契数列。题目假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。示...

187J3X1 2019-06-26 17:49 评论0 收藏0
【Leetcode】70. 爬楼梯

摘要：题目假设你正在爬楼梯。需要阶你才能到达楼顶。你有多少种不同的方法可以爬到楼顶呢注意给定是一个正整数。示例输入输出解释有两种方法可以爬到楼顶。阶阶阶阶阶阶阶题解这个题目只要模拟一下基本就能想到是，状态方程写出来就是斐波那契数列。题目假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。示...

wow_worktile 2019-07-25 14:26 评论0 收藏0
LeetCode 之 JavaScript 解答第70题 —— 爬楼梯（Climbing Stair

摘要：小鹿题目假设你正在爬楼梯。需要阶你才能到达楼顶。你有多少种不同的方法可以爬到楼顶呢注意给定是一个正整数。算法思路二种解决思路，第一利用递归第二利用动态规划。就是因为有了重复元素的计算，导致了时间复杂度成指数的增长。 Time：2019/4/12Title:Clibing SrairsDifficulty: EasyAuthor:小鹿题目：Climbing Stairs You a...

chemzqm 2019-08-23 16:55 评论0 收藏0
leetcode70 climbing stairs 爬楼梯游戏

摘要：题目要求假设有级台阶为正整数，每次可以爬一级台阶或两级台阶。问有多少种方法爬完级台阶递归方法最后一步可以是一级台阶，或者是两级台阶，一共两种情况。题目要求：假设有n级台阶（n为正整数），每次可以爬一级台阶或两级台阶。问有多少种方法爬完n级台阶？递归方法最后一步可以是一级台阶，或者是两级台阶，一共两种情况。可通过递归获得n-1级台阶和n-2级台阶的和获得n级台阶的结果台阶数量过高的话...

姘存按 2019-08-14 17:52 评论0 收藏0