【LeetCode】动态规划 刷题训练(一)

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

面试题 08.01. 三步问题

点击查看: 三步问题

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

示例1:
输入:n = 3
输出:4
说明: 有四种走法
示例2:
输入:n = 5
输出:13

题目解析

【LeetCode】动态规划 刷题训练(一)

当n==1时
只能从 0走到1 ,即0->1 , 所以只有1 种方法

当n==2时
可以从 0->2 ,有1种 方法
可以从 1->2 , 而0到1 只有1种方法,而1到2只需加一步,所以有2种方法
最终 1+1 ,共有2种方法

当n==3时
从0->3 有1种方法
从1->3 ,因为0->1只有1种方法,而1到3只需加一步 ,所以 有1种方法
从2->3,因为0->2有2种方法 ,而2到3只需加一步,所以有2种方法
最终 1+1+2 ,共有 4种方法

当n==4时
因为 最多一次 走 3步,所以 0->4 不成立
从1->4,因为0->1 有1种方法,而1到4只需加一步,所以有1种方法
从2->4,因为0->2 有2种方法,而2到4只需加一步,所以有2种方法
从3->4,因为0->3有3种方法,而3到4只需加一步,所以有3种方法
最终 1+2+3, 共有7种方法


状态转移方程

以i位置为结尾
dp[i]代表到达i位置时,共有多少种方法


状态转移方程
以 i 位置的状态,最近的一步划分问题

【LeetCode】动态规划 刷题训练(一)

dp[i]分三种情况考虑,
从i-1位置到i位置 即dp[i-1]
从i-2位置到i位置 即dp[i-2]
从i-3位置到i位置 即dp[i-3]

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

完整代码

class Solution {
public:
    int waysToStep(int n) {
    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;
    int i=0;
    for(i=4;i<=n;i++)
    {
        dp[i]=( (dp[i-1]+dp[i-2])%1000000007+dp[i-3])%1000000007;
    }
    return  dp[n];
    }
};

在计算状态转移方程时,不能将三个加一起后在取模 ,否则会报错
在 dp[i-1] 与dp[i-2] 相加时就需要取模,然后与dp[i-3]相加时 再取模


746. 使用最小花费爬楼梯

点击查看:使用最小花费爬楼梯

给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。

示例 1:
输入:cost = [10,15,20]
输出:15
解释:你将从下标为 1 的台阶开始。
支付 15 ,向上爬两个台阶,到达楼梯顶部。
总花费为 15 。

题目解析

【LeetCode】动态规划 刷题训练(一)
从下标0处开始,可以花费10块 到下标为1处 ,也可以到下标为2处
但是 下标为2处并不是 楼顶,因为此处若为楼顶的话,则最小花费应为10,而不是15 ,
所以楼顶为 cost 数组 最后一个元素的下一个


【LeetCode】动态规划 刷题训练(一)

从下标为1的位置开始,可以到下标为2处,也可以到楼顶处

状态转移方程

【LeetCode】动态规划 刷题训练(一)

dp[i] 代表 达到 i 位置时 的最小花费
而i位置 的最小花费,又是 通过 i-1位置 的最小花费 和 i-2位置的最小花费 综合的最小花费 而得来的


dp[i] 可以分为

1. 先达到i-1位置,支付coost[i-1],走一步
dp[i-1]代表 达到i-1位置的最小花费 ,cost[i-1]代表 i-1位置所需费用
dp[i-1]+cost[i-1]

2. 先达到 i-2位置,支付cost[i-2], 走两步
dp[i-2]代表 达到i-2位置的最小花费 ,cost[i-2]代表 i-2位置所需费用
dp[i-2]+cost[i-2]

动态转移方程
dp[i]= min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);

完整代码

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
      vector<int>dp(cost.size()+1,0);
      dp[0]=0;
      dp[1]=0;
      int i=0;
      for(i=2;i<cost.size()+1;i++)
      {
          dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
      }
      return dp[cost.size()];
    }
};

对于状态转移方程,下标为0和下标为1的位置是没办法使用的,会造成越界
题中说可以选择从0或者1位置开始爬楼梯 代表两个位置是没有花费的
dp[0] =0 ,dp[1]=0

91. 解码方法

点击查看:解码方法

一条包含字母 A-Z 的消息通过以下映射进行了 编码 :
‘A’ -> “1”
‘B’ -> “2”
‘Z’ -> “26”
要 解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法)。例如,“11106” 可以映射为:
“AAJF” ,将消息分组为 (1 1 10 6)
“KJF” ,将消息分组为 (11 10 6)
注意,消息不能分组为 (1 11 06) ,因为 “06” 不能映射为 “F” ,这是由于 “6” 和 “06” 在映射中并不等价。
给你一个只含数字的 非空 字符串 s ,请计算并返回 解码 方法的 总数 。
题目数据保证答案肯定是一个 32 位 的整数。

示例 1:
输入:s = “12”
输出:2
解释:它可以解码为 “AB”(1 2)或者 “L”(12)。

示例 3:
输入:s = “06”
输出:0
解释:“06” 无法映射到 “F” ,因为存在前导零(“6” 和 “06” 并不等价)。

题目解析

【LeetCode】动态规划 刷题训练(一)

若将其 分为1和2,则 分别对应 A和B
若 将其看作一个整体,则 对应为L


【LeetCode】动态规划 刷题训练(一)

若将其分为0和6,则0没有对应字母
若将其 看作一个整体,不允许 存在前导0 表示

状态转移方程

【LeetCode】动态规划 刷题训练(一)

dp[i] 表示 以i位置为结尾时,解码方法的总数

情况1:让i位置的数,单独去解码

单独解码的数 需要在1-9,所以会存在 成功/失败的情况

若解码成功,则i位置对应的数字 为1-9之间,相当于把0到i-1位置的所有解码方案 后面加上一个字符,
整体解码的数量就为以i-1位置结尾的数量 即dp[i-1]

若解码失败,则全部失败 ,解码数为0
如: 60 单独计算,6为F,而0不存在 对应数, 所以没有解码成功

情况2:让i位置的数 和i-1位置的数 结合 一起去解码

若解码成功,则结合的数字 为 10-26之间,相当于在0到i-2位置的所有解码方案 后面加上一个字符,
整体解码的数量就为 以i-2结尾的的数量 即dp[i-2]

若解码失败,则全部失败 ,解码数为0


dp[i]=dp[i-1]+dp[i-2]
dp[i-1] 和dp[i-2]只有在解码成功时,才会加上,否则为0

完整代码

class Solution {
public:
    int numDecodings(string s) {
       vector<int>dp(s.size());
        int i=0;

        //初始化
        if(s[0]!='0')
        {
            dp[0]=1;
        }
        else 
        {
            dp[0]=0;
        }
        
        //有可能s字符串只有一个数字 
        if(s.size()==1)
        {
            return dp[0];
        }

       if(s[0]!='0'&&s[1]!='0')
       {
           dp[1]++;
       }
       //因为s[0]存的是字符,所以选哟减去'0',从而获取数字
       int sum=(s[0]-'0')*10+(s[1]-'0');
       if(sum>=10&&sum<=26)
       {
           dp[1]++;
       }

        for(i=2;i<s.size();i++)
        {
            //说明可以单独编码成功
           if(s[i]!='0')
           {
             dp[i]+=dp[i-1];
           }

             //说明可以结合编码成功
            int sum=(s[i-1]-'0')*10+(s[i]-'0');
         
            if(sum>=10&&sum<=26)
            {
                dp[i]+=dp[i-2];
            }

        }
        return dp[s.size()-1];
    }
};

初始化
dp[0] 表示 只有一个数字
若数字 处于1-9之间,则解码成功,返回1
若数字 为0,则解码失败 ,返回0

dp[1] 表示 两个数字
可以分为 两个数字 单独解码 和 结合起来解码

若 单独解码 成功,则解码数+1,否则为0
若结合起来解码 成功,则解码数+1,否则为0
所以有 0 1 2 三种情况
文章来源地址https://www.toymoban.com/news/detail-497653.html

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

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

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

相关文章

  • 【LeetCode】动态规划 刷题训练(五)

    点击查看:粉刷房子 假如有一排房子,共 n 个,每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种,你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。 当然,因为市场上不同颜色油漆的价格不同,所以房子粉刷成不同颜色的花费成本也是不同的。

    2024年02月11日
    浏览(45)
  • 【LeetCode】动态规划 刷题训练(四)

    点击查看:按摩师 一个有名的按摩师会收到源源不断的预约请求,每个预约都可以选择接或不接。在每次预约服务之间要有休息时间,因此她不能接受相邻的预约。给定一个预约请求序列,替按摩师找到最优的预约集合(总预约时间最长),返回总的分钟数。 示例 1: 输入

    2024年02月11日
    浏览(36)
  • 【LeetCode】动态规划 刷题训练(二)

    点击查看:不同路径 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。 问总共有多少条不同的路径? 示例 1: 输入:m = 3, n = 7 输出:28 示例

    2024年02月10日
    浏览(36)
  • 【LeetCode】 动态规划 刷题训练(三)

    点击查看:下降路径最小和 给你一个 n x n 的 方形 整数数组 matrix ,请你找出并返回通过 matrix 的下降路径 的 最小和 。 下降路径 可以从第一行中的任何元素开始,并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列(即位于正下方或者沿对角线

    2024年02月10日
    浏览(41)
  • 3-【斐波那契数列模型】LeetCode面试题08.01-三步问题

    题目 三步问题。有个小孩正在上楼梯,楼梯有n阶台阶,小孩一次可以上1阶、2阶或3阶。实现一种方法,计算小孩有多少种上楼梯的方式。结果可能很大,你需要对结果模1000000007。 示例1: 输入:n = 3  输出:4 说明: 有四种走法 示例2: 输入:n = 5 输出:13 提示:n范围在[1, 1000

    2024年02月05日
    浏览(41)
  • 动态规划01 三步问题[C++]

      ​​​​​​ 图源:文心一言 上机题目练习整理,本篇作为动态规划的代码,因为做题入门很少找到带图的讲解(难道是因为太简单,所以没有人嘛),所以干脆自己写一份,供小伙伴们参考~🥝🥝 第1版:在力扣新手村刷题的记录~🧩🧩 编辑: 梅头脑🌸 审核: 文心一

    2024年03月15日
    浏览(35)
  • LeetCode三步问题(动态规划)

    链接: 三步问题 编写代码 代码优化

    2024年02月15日
    浏览(41)
  • 【动态规划刷题 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日
    浏览(39)
  • 《动态规划》刷题训练

    你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统, 如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动

    2024年01月19日
    浏览(45)
  • 面试题 08.01. 三步问题

    ​​ 题目来源:         leetcode题目,网址:面试题 08.01. 三步问题 - 力扣(LeetCode) 解题思路:         动态规划。1 阶楼梯 1 种走法,2 阶楼梯 2 种走法,3 阶楼梯 6 种类走法。假设有 n(n3) 阶楼梯,n-1 阶楼梯有 a 种走法,n-2 阶楼梯有 b 种走法,n-3 阶楼梯有 c 种走法,则

    2024年02月10日
    浏览(32)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包