2024华为校招面试真题汇总及其解答（二）

6.【算法题】三步问题

题目：

三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。

示例1:

 输入：n = 3 
 输出：4
 说明: 有四种走法

示例2:

 输入：n = 5
 输出：13

提示:

1. n范围在[1, 1000000]之间

解答：

这是一个动态规划问题。我们可以用一个数组来存储每个阶梯的走法数量，数组的下标表示阶梯的高度，数组的值表示走到该阶梯的走法数量。

初始条件：

• 数组的第一个元素为1，表示只有一个阶梯时，只有一种走法。
• 数组的第二个元素为2，表示有两个阶梯时，有两种走法。

状态转移方程：

• 数组的第i个元素表示有i阶梯时，走法数量。
• 数组的第i个元素等于数组的第i-1个元素加上数组的第i-2个元素加上数组的第i-3个元素。

例如，当n = 3时，数组的状态如下：

[1, 2, 4]

解释：