LeetCode 面试题 08.01. 三步问题

Categories:

题目描述
思路分析
1. 解法一：滚动 DP（推荐）
相似题目

题目描述

✅ 面试题 08.01. 三步问题

思路分析

解法一：滚动 DP（推荐）

核心思路：

设 f[i] = f[i-1] + f[i-2] + f[i-3]。

用滚动数组保留最近三项即可。

每步对 1e9+7 取模。

复杂度分析：

时间复杂度：O(n)，其中 n 表示步数。

空间复杂度：O(1)。

class Solution {
    private static final int MOD = 1_000_000_007;

    public int waysToStep(int n) {
        if (n <= 2) {
            return n;
        }
        if (n == 3) {
            return 4;
        }

        long a = 1;
        long b = 2;
        long c = 4;
        for (int i = 4; i <= n; i++) {
            long d = (a + b + c) % MOD;
            a = b;
            b = c;
            c = d;
        }
        return (int) c;
    }
}

func waysToStep(n int) int {
	const mod int64 = 1_000_000_007
	if n <= 2 {
		return n
	}
	if n == 3 {
		return 4
	}

	a, b, c := int64(1), int64(2), int64(4)
	for i := 4; i <= n; i++ {
		d := (a + b + c) % mod
		a, b, c = b, c, d
	}
	return int(c)
}

相似题目

题目	难度	考察点
70. 爬楼梯	简单	DP
746. 使用最小花费爬楼梯	简单	DP
198. 打家劫舍	中等	DP
509. 斐波那契数	简单	DP
1137. 第 N 个泰波那契数	简单	DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/56793616