每日算法:爬楼梯问题

时间:2022-09-10 12:56:04

每日算法:爬楼梯问题

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

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

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

示例 1:

  1. 输入:2
  2. 输出:2
  3. 解释:有两种方法可以爬到楼顶。
  4. 1.1阶+1阶
  5. 2.2阶

示例 2:

  1. 输入:3
  2. 输出:3
  3. 解释:有三种方法可以爬到楼顶。
  4. 1.1阶+1阶+1阶
  5. 2.1阶+2阶
  6. 3.2阶+1阶

解法:动态规划

动态规划(Dynamic Programming,DP)是一种将复杂问题分解成小问题求解的策略,但与分治算法不同的是,分治算法要求各子问题是相互独立的,而动态规划各子问题是相互关联的。

分治,顾名思义,就是分而治之,将一个复杂的问题,分成两个或多个相似的子问题,在把子问题分成更小的子问题,直到更小的子问题可以简单求解,求解子问题,则原问题的解则为子问题解的合并。

我们使用动态规划求解问题时,需要遵循以下几个重要步骤:

  • 定义子问题
  • 实现需要反复执行解决的子子问题部分
  • 识别并求解出边界条件

第一步:定义子问题

如果用 dp[n] 表示第 n 级台阶的方案数,并且由题目知:最后一步可能迈 2 个台阶,也可迈 1 个台阶,即第 n 级台阶的方案数等于第 n-1 级台阶的方案数加上第 n-2 级台阶的方案数

第二步:实现需要反复执行解决的子子问题部分

  1. dp[n]=dp[n−1]+dp[n−2]

第三步:识别并求解出边界条件

  1. //第0级1种方案
  2. dp[0]=1
  3. //第1级也是1种方案
  4. dp[1]=1

最后一步:把尾码翻译成代码,处理一些边界情况

  1. letclimbStairs=function(n){
  2. letdp=[1,1]
  3. for(leti=2;i<=n;i++){
  4. dp[i]=dp[i-1]+dp[i-2]
  5. }
  6. returndp[n]
  7. }

复杂度分析:

  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

优化空间复杂度:

  1. letclimbStairs=function(n){
  2. letres=1,n1=1,n2=1
  3. for(leti=2;i<=n;i++){
  4. res=n1+n2
  5. n1=n2
  6. n2=res
  7. }
  8. returnres
  9. }

空间复杂度: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