【学会动态规划】三步问题(2)

这篇具有很好参考价值的文章主要介绍了【学会动态规划】三步问题(2)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

动态规划怎么学?

1. 题目解析

2. 算法原理

1. 状态表示

2. 状态转移方程

3. 初始化

4. 填表顺序

5. 返回值

3. 代码编写

写在最后:


动态规划怎么学?

学习一个算法没有捷径,更何况是学习动态规划,

跟我一起刷动态规划算法题,一起学会动态规划!

1. 题目解析

【学会动态规划】三步问题(2),动态规划,算法,c++

根据题目,我们可以模拟一下走楼梯的过程,

比如说这里有四级台阶:

【学会动态规划】三步问题(2),动态规划,算法,c++

小孩走到一级台阶有一种走法,就是直接走上去:

【学会动态规划】三步问题(2),动态规划,算法,c++

小孩走到二级台阶有两种走法,一种是直接走上去,

一种是以一级台阶作为起点,一步走上去:

【学会动态规划】三步问题(2),动态规划,算法,c++

 小孩走到三级台阶有四种走法:

从平地直接走上去,这是一种走法;

以一级台阶为起点,而走到一级台阶有一种方法,所以从一级台阶直接走上去是一种走法;

以二级台阶为起点,而到二级台阶有两种方法,所以以二级台阶为起点是两种方法;

1 + 1 + 2 = 4 种方法:

【学会动态规划】三步问题(2),动态规划,算法,c++

 小孩走到四级台阶有七种走法:

以一级台阶为起点,是一种方法;

以二级台阶为起点,有两种方法;

以三级台阶为起点,有四种方法:

1 + 2 + 4 = 7 种方法:

【学会动态规划】三步问题(2),动态规划,算法,c++

现在是不是发现规律了,

实际上就是前面三个数相加。 

2. 算法原理

1. 状态表示

根据我们之前学的,状态表示就是指:dp[ i ] 表示的是什么?

而 dp[ i ] 表示的是:到达 i 位置时,一共有多少种走法。

2. 状态转移方程

那么 dp[ i ] 等于什么呢?

根据前面找到规律,我们不难得出:

dp[ i ] = dp[ i - 3 ] + dp[ i - 2 ] + dp[ i - 1 ]

3. 初始化

初识化就靠我们自己刚刚算的:

dp[ 1 ] = 1,dp[ 2 ] = 2,dp[ 3 ] = 4。

4. 填表顺序

一步步上台阶,就是从左往右填。

5. 返回值

返回的就是 dp[ n ] 位置的值

3. 代码编写

代码编写其实就是按照我们之前的分析,

用固定的套路编写就行:

class Solution {
public:
    int waysToStep(int n) {
        // dp 题目的固定写代码套路
        // 1. 创建dp表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值

        const int MOD = 1e9 + 7;
        //考虑边界问题
        if(n == 1 || n == 2) return n;
        if(n == 3) return 4;

        vector<int> dp(n + 1);
        dp[1] = 1, dp[2] = 2, dp[3] = 4;
        for(int i = 4; i <= n; i++) {
            dp[i] = ((dp[i - 3] + dp[i - 2]) % MOD + dp[i - 1]) % MOD;
        }
        return dp[n];
    }
};

写在最后:

以上就是本篇文章的内容了,感谢你的阅读。

如果感到有所收获的话可以给博主点一个哦。

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~文章来源地址https://www.toymoban.com/news/detail-567227.html

到了这里,关于【学会动态规划】三步问题(2)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【动态规划刷题 1 】 第N个泰波那契数&& 三步问题

    链接: 第N个泰波那契数 1137 . 第 N 个泰波那契数 泰波那契序列 Tn 定义如下: T0 = 0, T1 = 1, T2 = 1, 且在 n = 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2 给你整数 n,请返回第 n 个泰波那契数 Tn 的值。 示例 1: 输入:n = 4 输出:4 解释: T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4 示例 2: 输入:n = 25 输出:

    2024年02月15日
    浏览(40)
  • 60题学会动态规划系列:动态规划算法第三讲

    简单多状态问题 文章目录 一.按摩师 二.打家劫舍系列 三.删除并获得点数 四.粉刷房子 力扣链接:力扣 一个有名的按摩师会收到源源不断的预约请求,每个预约都可以选择接或不接。在每次预约服务之间要有休息时间,因此她不能接受相邻的预约。给定一个预约请求序列,

    2024年02月08日
    浏览(49)
  • 60题学会动态规划系列:动态规划算法第四讲

    买卖股票相关的动态规划题目 文章目录 1. 买卖股票的最佳时机含冷冻期 2. 买卖股票的最佳时期含⼿续费 3. 买卖股票的最佳时机III 4. 买卖股票的最佳时机IV 力扣链接:力扣 给定一个整数数组 prices ,其中第    prices[i]  表示第  i  天的股票价格 。​ 设计一个算法计算出最

    2024年02月13日
    浏览(36)
  • 60题学会动态规划系列:动态规划算法第五讲

    子数组系列题目 文章目录 1.最大子数组和 2.环形子数组的最大和 3.乘积最大数组 4.乘积为正数的最长子数组长度 5.等差数列划分 6.最长湍流子数组 7.单词拆分 8.环绕字符串中唯一的子字符串 力扣链接:力扣 给你一个整数数组  nums  ,请你找出一个具有最大和的连续子数组(

    2024年02月15日
    浏览(69)
  • 60题学会动态规划系列:动态规划算法第一讲

    坚持就是胜利 - -  文章目录 1.第N个泰波那切数 2.三步问题 3.使用最小花费爬楼梯 4.解码方法 力扣链接:力扣 泰波那契序列 Tn 定义如下:  T0 = 0, T1 = 1, T2 = 1, 且在 n = 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2 给你整数  n ,请返回第 n 个泰波那契数 Tn 的值。  首先我们分析一下

    2024年02月06日
    浏览(45)
  • 60题学会动态规划系列:动态规划算法第二讲

    都是路径问题~ 文章目录 1.不同路径 2.不同路径II 3.礼物的最大价值 4.下降路径最小和 5.最小路径和 力扣链接:力扣 一个机器人位于一个  m x n   网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在

    2024年02月07日
    浏览(59)
  • 上升子序列的最大长度,递归-记忆化搜索-动态规划三步走

    题目描述: 小明有一个数组,他想从数组任意元素开始向后遍历,找出所有上升子序列,并计算出最长的上升子序列的长度。 数据范围: 每组数据长度满足 1≤n≤200 1≤n≤200 , 数据大小满足 1≤val≤350 1≤val≤350 输入描述: 数据共2行,第1行先输入数组的个数,第2行再输

    2024年04月22日
    浏览(42)
  • 【算法-动态规划】0-1 背包问题

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月08日
    浏览(47)
  • 【算法专题】动态规划之路径问题

    题目链接 - Leetcode -62.不同路径 Leetcode -62.不同路径 题目:一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。 问总共有多少条不同的路径? 示

    2024年01月24日
    浏览(48)
  • 【算法 - 动态规划】找零钱问题Ⅲ

    在前面的动态规划系列文章中,关于如何对递归进行分析的四种基本模型都介绍完了,再来回顾一下: 从左到右模型 : arr[index ...] 从 index 之前的不用考虑, 只考虑后面的该如何选择 。 范围尝试模型 :思考 [L ,R] 两端,即 开头和结尾 处分别该如何取舍。 样本对应模型 :

    2024年04月09日
    浏览(43)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包