假设你正在爬楼梯。需要 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阶
解法:动态规划
动态规划(Dynamic Programming,DP)是一种将复杂问题分解成小问题求解的策略,但与分治算法不同的是,分治算法要求各子问题是相互独立的,而动态规划各子问题是相互关联的。
分治,顾名思义,就是分而治之,将一个复杂的问题,分成两个或多个相似的子问题,在把子问题分成更小的子问题,直到更小的子问题可以简单求解,求解子问题,则原问题的解则为子问题解的合并。
我们使用动态规划求解问题时,需要遵循以下几个重要步骤:
- 定义子问题
- 实现需要反复执行解决的子子问题部分
- 识别并求解出边界条件
第一步:定义子问题
如果用 dp[n] 表示第 n 级台阶的方案数,并且由题目知:最后一步可能迈 2 个台阶,也可迈 1 个台阶,即第 n 级台阶的方案数等于第 n-1 级台阶的方案数加上第 n-2 级台阶的方案数
第二步:实现需要反复执行解决的子子问题部分
- dp[n]=dp[n−1]+dp[n−2]
第三步:识别并求解出边界条件
- //第0级1种方案
- dp[0]=1
- //第1级也是1种方案
- dp[1]=1
最后一步:把尾码翻译成代码,处理一些边界情况
- letclimbStairs=function(n){
- letdp=[1,1]
- for(leti=2;i<=n;i++){
- dp[i]=dp[i-1]+dp[i-2]
- }
- returndp[n]
- }
复杂度分析:
- 时间复杂度:O(n)
- 空间复杂度:O(n)
优化空间复杂度:
- letclimbStairs=function(n){
- letres=1,n1=1,n2=1
- for(leti=2;i<=n;i++){
- res=n1+n2
- n1=n2
- n2=res
- }
- returnres
- }
空间复杂度:O(1)
leetcode:https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-wen-ti-by-user7746o/
原文链接:https://mp.weixin.qq.com/s/W9-JRtMehbb0zy_QpJUZbw