3-【斐波那契数列模型】LeetCode面试题08.01-三步问题

这篇具有很好参考价值的文章主要介绍了3-【斐波那契数列模型】LeetCode面试题08.01-三步问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

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

示例1:

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

示例2:

输入:n = 5
输出:13

提示:n范围在[1, 1000000]之间


思路

  • 到0阶台阶的方式:(地平线)
  • 到1阶台阶的方式:1种(0->1)
  • 到2阶台阶的方式:2种(0->2、到1阶台阶的方式1种(0->1->2))
  • 到3阶台阶的方式:4种(0->3、到1阶台阶的方式1种、到2阶台阶的方式2种)
  • 到4阶台阶的方式:7种(到1阶台阶的方式1种、到2阶台阶的方式2种、到3阶台阶的方式4种)
  • 到5阶台阶的方式:13种
  • ......

step1:状态表示

经验(以某一个位置为起点或结尾)+题目要求(做替换即可):

dp[i]表示:到达i位置时,一共有多少种方式。

step2:状态转移方程

以i位置的最近一次位置来划分问题——dp[i]有3种情况:

  1. 从i - 3位置跳3步一次性到达i位置。到i - 3位置有dp[i - 3]种方式,后面再加一步到i位置,则到i位置有dp[i - 3]种方式。
  2. 从i - 2位置跳2步一次性到达i位置。同理:则到i位置有dp[i - 2]种方式。
  3. 从i - 1位置跳1步一次性到达i位置。同理:则到i位置有dp[i - 1]种方式。

得状态转移方程为:dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]。

step3:初始化

令dp[1] = 1、dp[2] = 2、dp[3] = 4,这样就不会越界。

step4:填表顺序

从左往右。

step5:返回值

返回dp[n]。


代码文章来源地址https://www.toymoban.com/news/detail-454963.html

class Solution {
    public int waysToStep(int n) {
        int MOD = (int)1e9 + 7;

        //处理边界条件
        if(n == 1 || n == 2) {
            return n;
        }
        if(n == 3) {
            return 4;
        }

        //1.创建 dp 表
        int[] dp = new int[n + 1]; //要访问到 n 的位置,所以 dp 表规模要是 n + 1 大小

        //2.初始化
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;

        //3.填表
        for(int i = 4; i <= n; i++) {
            dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;
        }
        
        //4.返回值
        return dp[n];
    }
}

到了这里,关于3-【斐波那契数列模型】LeetCode面试题08.01-三步问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++算法 —— 动态规划(1)斐波那契数列模型

    每一种算法都最好看完第一篇再去找要看的博客,因为这样会帮你梳理好思路,看接下来的博客也就更轻松了。当然,我也会尽量在写每一篇时都可以让不懂这个算法的人也能边看边理解。 动规的思路有五个步骤,且最好画图来理解细节,不要怕麻烦。当你开始画图,仔细阅

    2024年02月10日
    浏览(44)
  • 【动态规划专栏】专题一:斐波那契数列模型--------1.第N个泰波那契数

    本专栏内容为:算法学习专栏,分为优选算法专栏,贪心算法专栏,动态规划专栏以及递归,搜索与回溯算法专栏四部分。 通过本专栏的深入学习,你可以了解并掌握算法。 💓博主csdn个人主页:小小unicorn ⏩专栏分类:动态规划专栏 🚚代码仓库:小小unicorn的代码仓库🚚

    2024年02月21日
    浏览(42)
  • (动态规划) 剑指 Offer 10- I. 斐波那契数列 ——【Leetcode每日一题】

    难度:简单 写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项(即 F(N) )。斐波那契数列的定义如下: F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N 1. 斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。 答案需要取模 1e9+7(1000000007),如计

    2024年02月12日
    浏览(51)
  • 动态规划入门:斐波那契数列模型以及多状态(C++)

        动态规划(Dynamic programming,简称 DP)是一种解决多阶段决策问题的算法思想。它将问题分解为多个阶段,并通过保存中间结果来避免重复计算,从而提高效率。 动态规划的解题步骤一般分为以下几步: 思考状态表示,创建dp表(重点) 分析出状态转移方程(重点) 初始化 确定

    2024年02月11日
    浏览(42)
  • Java【动态规划】斐波那契数列模型, 图文思路详解 + 代码实现

    本篇总结动态规划中的 斐波那契数列模型 的解法和思路 按照以下流程进行分析题目和代码编写 思路分析步骤 代码编写步骤 1, 状态表示 1, 构造 dp 表 2, 状态转移方程 2, 初始化+边界处理 3, 初始化 3, 填表(抄状态转移方程) 4, 填表顺序 4, 返回结果 5, 返回值 / OJ链接 题目分析

    2024年02月08日
    浏览(57)
  • 【动态规划专栏】专题一:斐波那契数列模型--------2.三步问题

    本专栏内容为:算法学习专栏,分为优选算法专栏,贪心算法专栏,动态规划专栏以及递归,搜索与回溯算法专栏四部分。 通过本专栏的深入学习,你可以了解并掌握算法。 💓博主csdn个人主页:小小unicorn ⏩专栏分类:动态规划专栏 🚚代码仓库:小小unicorn的代码仓库🚚

    2024年02月21日
    浏览(46)
  • JAVA-斐波那契数列

    输入一个整数 n ,求斐波那契数列的第 n 项。 假定从 0 开始,第 0 项为 0 。 数据范围 0≤n≤39 样例

    2024年02月10日
    浏览(51)
  • Python斐波那契数列

    斐波那契数列是一个经典的数学问题,在 Python 中可以使用多种方法来实现,下面是几个常见的实现方式: 1. 使用递归 ```python def fibonacci_recursive(n):     if n = 1:         return n     else:         return fibonacci_recursive(n-1) + fibonacci_recursive(n-2) ``` 2. 使用循环 ```python def fibonacci_i

    2024年02月02日
    浏览(44)
  • 斐波那契数列应用2

    目录 斐波那契数列应用2 程序设计 程序分析  系列文章 【问题描述】定义如下序列:f(1)=1,f(2)=1;f(n)=(A*f(n-1)+B*f(n-2))mod7     给定A和B,请你计算f(n)的值。 【输

    2023年04月10日
    浏览(52)
  • 矩阵快速幂&斐波那契数列

    矩阵快速幂: 快速地求出斐波那契数列中的每一项 可以快速地求出斐波那契数列的前n项的和 首先我们来看如何快速地求出斐波那契数列的第n项 设 F n = [ f n , f n + 1 ] F_n = [f_n,f_{n+1}] F n ​ = [ f n ​ , f n + 1 ​ ] ,构造这一个行向量,那么对于此,我们思考 F n F_n F n ​ 乘一个

    2024年02月06日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包