摘要:题目假设你正在爬楼梯。需要阶你才能到达楼顶。你有多少种不同的方法可以爬到楼顶呢注意给定是一个正整数。示例输入输出解释有两种方法可以爬到楼顶。阶阶阶阶阶阶阶题解这个题目只要模拟一下基本就能想到是,状态方程写出来就是斐波那契数列。
题目
假设你正在爬楼梯。需要 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
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. 加一
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/40108.html
摘要:题目假设你正在爬楼梯。需要阶你才能到达楼顶。你有多少种不同的方法可以爬到楼顶呢注意给定是一个正整数。示例输入输出解释有两种方法可以爬到楼顶。阶阶阶阶阶阶阶题解这个题目只要模拟一下基本就能想到是,状态方程写出来就是斐波那契数列。 题目 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数。 示...
摘要:题目假设你正在爬楼梯。需要阶你才能到达楼顶。你有多少种不同的方法可以爬到楼顶呢注意给定是一个正整数。示例输入输出解释有两种方法可以爬到楼顶。阶阶阶阶阶阶阶题解这个题目只要模拟一下基本就能想到是,状态方程写出来就是斐波那契数列。 题目 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数。 示...
摘要:小鹿题目假设你正在爬楼梯。需要阶你才能到达楼顶。你有多少种不同的方法可以爬到楼顶呢注意给定是一个正整数。算法思路二种解决思路,第一利用递归第二利用动态规划。就是因为有了重复元素的计算,导致了时间复杂度成指数的增长。 Time:2019/4/12Title:Clibing SrairsDifficulty: EasyAuthor:小鹿 题目:Climbing Stairs You a...
摘要:题目要求假设有级台阶为正整数,每次可以爬一级台阶或两级台阶。问有多少种方法爬完级台阶递归方法最后一步可以是一级台阶,或者是两级台阶,一共两种情况。 题目要求:假设有n级台阶(n为正整数),每次可以爬一级台阶或两级台阶。问有多少种方法爬完n级台阶? 递归方法最后一步可以是一级台阶,或者是两级台阶,一共两种情况。可通过递归获得n-1级台阶和n-2级台阶的和获得n级台阶的结果台阶数量过高的话...
阅读 2041·2023-04-25 15:11
阅读 3461·2021-09-23 11:57
阅读 1372·2021-07-26 23:38
阅读 1319·2019-08-30 15:54
阅读 635·2019-08-30 15:53
阅读 3245·2019-08-26 13:36
阅读 986·2019-08-26 12:01
阅读 2863·2019-08-23 16:21