使用步骤1、2或3计算到达第n个楼梯的方式  


难度级别 易得奖学金
经常问 亚马逊 编码国家 GE医疗集团 微软 月蛙实验室 贝宝 尤伯杯
组合式 动态编程

问题“计算使用第1步,第2步或第3步到达第n个楼梯的方式”表示您站在地面上。 现在您需要到达楼梯的尽头。 那么,如果您只能跳1、2或3步,到底有多少种方法可以到达终点?

使用案列  

使用步骤1、2或3计算到达第n个楼梯的方式Pin

2
2

说明

有两种方法,因为我们要么直接从地面直接到达第二步,要么首先到达第一阶梯然后向前移动。

途径  

这个问题问我们从楼梯开始到达楼梯尽头的总数不同。 因此考虑楼梯有2个步骤。 然后有2种可能的方法,您可以直接进入第二步,或者第一步进入第一步,然后再进入第二步。 同样,我们需要计算使用步骤2、1或2到达第n个楼梯的方式。

天真的方法是生成所有可能的方法,然后计算它们。 但是这种方法将很耗时。 因此,为了减少时间复杂度,我们必须考虑一些不同的方法。 我们在朴素方法中讨论的方法是 递归 您可以从第0步开始的解决方案。 然后在每个递归调用中,转到步骤i + 1,i + 2和i + 3。 当您到达第n步时,递增计数器。 最终,计数器以这种方式存储了到达第n步的方式的数量。 但是此步骤一次又一次地重新计算了相同的问题。 因此,为了优化此解决方案,我们使用 动态编程.

参见
子序列增加的最大乘积

在动态编程解决方案中,我们认为我们站在第i步。 那么到达第i步的方式有i-1步,i-2步或i-3步。 因此,从形式上讲,使用此递归公式,Ways [i] = Ways [i-1] + Ways [i-2] + Ways [i-3]。 我们将解决我们的问题。

代码  

C ++代码使用步骤1、2或3计算到达第n个楼梯的方式

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;cin>>n;
    int dp[n+1];
    // base case
    dp[0] = 1;
    for(int i=1;i<=n;i++){
        dp[i] = ((i-1)>=0 ? dp[i-1] : 0) +
                ((i-2)>=0 ? dp[i-2] : 0) +
                ((i-3)>=0 ? dp[i-3] : 0);
    }
    cout<<dp[n];
}
5
13

Java代码使用步骤1、2或3计算到达第n个楼梯的方式

import java.util.*;
class Main{
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
  int n = sc.nextInt();
    int dp[] = new int[n+1];
    // base case
    dp[0] = 1;
    for(int i=1;i<=n;i++){
        dp[i] = ((i-1)>=0 ? dp[i-1] : 0) +
                ((i-2)>=0 ? dp[i-2] : 0) +
                ((i-3)>=0 ? dp[i-3] : 0);
    }

    System.out.print(dp[n]);
  }
}
5
13

复杂度分析  

时间复杂度

上), 因为我们必须循环运行直到第n步。 因此,就动态规划而言,我们具有从0到n的单个状态,转换成本为O(1)。 因此,时间复杂度是线性的。

空间复杂度

上), 因为我们需要创建一维DP阵列。 解决方案的空间复杂度是线性的。