leetcode
leetcode 2801 ~ 2850
三步问题

三步问题

难度:

标签:

题目描述

A child is running up a staircase with n steps and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs. The result may be large, so return it modulo 1000000007.

Example1:

 Input: n = 3 
 Output: 4

Example2:

 Input: n = 5
 Output: 13

Note:

  1. 1 <= n <= 1000000

代码结果

运行时间: 38 ms, 内存: 16.2 MB


/*
 * 思路：
 * 我们使用Java Stream来计算dp数组的值。每次递增求和的过程中，我们用一个窗口表示前3个值。
 * 使用IntStream.iterate来生成流，并使用takeWhile限制流的长度。
 */
import java.util.stream.IntStream;

public class Solution {
    public int waysToStep(int n) {
        int MOD = 1000000007;
        return IntStream.iterate(1, i -> i <= n, i -> i + 1)
                        .mapToObj(i -> i <= 2 ? (i == 2 ? 2 : 1) : (waysToStep(i - 1) + waysToStep(i - 2) + waysToStep(i - 3)) % MOD)
                        .reduce((first, second) -> second)
                        .orElse(1);
    }
}

解释

方法:

本题的解决方案采用矩阵快速幂来解决上楼梯问题。首先将问题转化为状态转移方程，其中每个状态表示从前一级、前两级或前三级台阶达到当前台阶的方式。接着，使用一个转移矩阵将这种状态转移表达出来，然后通过矩阵的快速幂求解来获得第n阶的计算结果。矩阵的快速幂使得我们可以在对数时间内得到结果，避免了线性时间上的计算。

时间复杂度:

O(log n)

空间复杂度:

O(1)

代码细节讲解

🦆
在矩阵快速幂的实现中，如何确保在反复矩阵乘法操作中不会产生整数溢出？
▷
在矩阵快速幂的实现过程中，为了避免整数溢出，每次矩阵乘法计算时，都会对结果进行模运算 `MOD = 10**9 + 7`。这个模运算是在乘法累加的每一步之后立即进行的，确保每个中间结果都不会超过模数，从而防止了在后续计算中的整数溢出。
🦆
在题解中提到的状态转移方程是如何从题目描述中得出的？具体是哪些状态在进行转移？
▷
状态转移方程源于解决上楼梯问题，其中可以从前一级、前两级或前三级台阶上到当前台阶。定义状态 dp[i] 为到达第 i 级台阶的方法数量。状态转移方程为 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。在矩阵表达中，这转化为使用一个转移矩阵 m = [[1, 1, 1], [1, 0, 0], [0, 1, 0]]，其中每个元素 m[i][j] 表示 dp[j] 对 dp[i] 的贡献。
🦆
为什么最终结果只需要返回矩阵乘法结果中的第一行第一列的值？这个值代表的具体含义是什么？
▷
最终结果只需返回矩阵乘法结果中的第一行第一列的值，因为这个值代表从基状态 (即 dp[1], dp[2], dp[3]) 到达第 n 级台阶的方法总数。在矩阵 m 的乘幂表示中，第一行的元素累积了所有可能的到达第 n 级台阶的路径，因此 matrix_pow_mod(m, n)[0][0] 正是我们需要的达到第 n 级台阶的方式数。

相关问题

绘制直线幂集