【LeetCode】--- 动态规划 集训(一)

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

一、1137. 第 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
输出:1389537

1.1 题目解析

因为要求的是第n个泰波那契序列,所以我们可以创建一个长度为 n 的dp表,用来表示第i位置的泰波那契序列(即:dp[i]表示:第 i 个泰波那契序列的值)。

接下来便是初始化,因为 dp[i]位置是前三个数的和,所以为了后序填表时不越界,要先初始化前三个数。题目中已给出前三个值,完成初始化即可(dp[0] = 0; dp[1] = dp[2] = 1;)。

填表顺序是:从左到右,依次填表。从下标为 3 的位置开始填表。

返回值为:dp[n],即第 n 个位置的泰波那契序列的值。还需要注意的小细节是,当序列长度不足 3 时,要单独判断返回值。

1.2 状态转移方程

依据题目要求(已给出):dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];

1.3 解题代码

class Solution 
{
public:
    int tribonacci(int n) 
    {
        //1. 创建dp表
        //2. 初始化
        //3. 填表
        //4. 返回结束

        if(n == 0) return 0;
        if(n == 1 || n == 2) return 1;

        vector<int> dp(n + 1);
        dp[0] = 0, dp[1] = dp[2] = 1;

        for(int i = 3; i <= n ; ++i)
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        return dp[n];
    }
};

二、面试题 08.01. 三步问题

题目地址: 面试题 08.01. 三步问题


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

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

2.1 题目解析

为了求到第 n 级台阶的方法数,可以定义一个长度为 n+1 的dp表,dp[i]表示:到 i 位置时,一共有多少种方法。

状态转移方程的确立,因为小孩可以一次走一级,两级或三级台阶,所以他可以从第 n-1, n-2 或 n-3 级台阶上到第 n 级台阶。所以到第 n 级台阶的总方法数,是到上述三种台阶的方法数总和。(以 i 位置的状态,最近的一步,来划分问题

【LeetCode】--- 动态规划 集训(一),数据结构和算法,leetcode,动态规划,算法,数据结构

接下来便是初始化,为了在填 dp 表时不越界(即取dp[i - 3]时),所以需要初始化前三个状态表的值(dp[1] = 1, dp[2] = 2, dp[3] = 4;)。还可以再多开一个位置,使台阶序号和 dp 表对应。

填表顺序:从左到右依次填表,从下标为 4 的位置开始填。

返回值:返回 dp[n],即到第 n 级台阶的方法数。n <= 3 时要单独判断,因为状态表从下标为 4 位置开始判断(利用最近的前三个状态)

2.2 状态转移方程

依据题目要求:dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];。还需要注意的是为了防止越界,顺应题目要求,要对结果模1000000007。那么便可写成如下格式:dp[i] = ((dp[i - 1] + dp[i - 2]) % num + dp[i - 3]) % num;

2.3 解题代码

class Solution 
{
public:
    int waysToStep(int n) 
    {
        //1. 创建dp表
        //2. 初始化
        //3. 填表
        //4. 返回结束

        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 num = 1e9 + 7;
        for(int i = 4; i <= n; ++i)
            dp[i] = ((dp[i - 1] + dp[i - 2]) % num + dp[i - 3]) % num;

            return dp[n];
    }
};

三、746. 使用最小花费爬楼梯

题目地址: 746. 使用最小花费爬楼梯


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

示例 1:
输入:cost = [10,15,20]
输出:15
解释:你将从下标为 1 的台阶开始。

  • 支付 15 ,向上爬两个台阶,到达楼梯顶部。

总花费为 15 。

示例 2:
输入:cost = [1,100,1,1,1,100,1,1,100,1]
输出:6
解释:你将从下标为 0 的台阶开始。

  • 支付 1 ,向上爬两个台阶,到达下标为 2 的台阶。
  • 支付 1 ,向上爬两个台阶,到达下标为 4 的台阶。
  • 支付 1 ,向上爬两个台阶,到达下标为 6 的台阶。
  • 支付 1 ,向上爬一个台阶,到达下标为 7 的台阶。
  • 支付 1 ,向上爬两个台阶,到达下标为 9 的台阶。
  • 支付 1 ,向上爬一个台阶,到达楼梯顶部。

总花费为 6 。

3.1 题目解析

此题所求的是达到楼梯顶部的最低花费,那么我们便可定义一个长度为 n+1 的 dp 状态表。多开一个是因为,此处的楼梯顶部,不是数组cost.size(),而是最后一个位置的下一个。那么我们便可使用,dp[i]来表示:到达 i 位置时,最小花费。

状态转移方程的确立,可以根据最小花费,因为一次可以向上爬一个或两个台阶。那么到达第 i 级台阶的最小花费,便可用最近的状态推导 dp[i]即:1. 先到达 i - 1位置,然后支付cost[i - 1],走一步(dp[i - 1] + cost[i - 1]); 2. 先到达 i - 2位置,然后支付cost[i - 2],走两步(dp[i - 2] + cost[i - 2])。然后求两者最小值,这便是到达第 i 级台阶的最小费用。

【LeetCode】--- 动态规划 集训(一),数据结构和算法,leetcode,动态规划,算法,数据结构

初始化:为了后序填表不越界,且初始化的值不影响填表,所以可将前两个状态初始化为0(dp[0] = dp[1] = 0;)。

填表顺序:从左到右,依次填表。从下标为 2 的位置开始填。

返回值dp[n]即是到达楼梯顶部的最低费用。

3.2 状态转移方程

依据题目要求:dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i -2]);文章来源地址https://www.toymoban.com/news/detail-843301.html

3.3 解题代码

class Solution 
{
public:
    int minCostClimbingStairs(vector<int>& cost) 
    {
        //1. 创建dp表
        //2. 初始化
        //3. 填表
        //4. 返回结束

        int n = cost.size();
        vector<int> dp(n + 1);
        dp[0] = 0, dp[1] = 0;

        for(int i = 2; i <= n; ++i)
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        return dp[n];
    }
};

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

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

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

相关文章

  • Java数据结构与算法----动态规划(背包篇)

    1.1.算法思路 0/1背包是动态规划、背包问题中最经典的问题啦!它主要的问题是: 给定n种物品、这n种物品的重量分别是,价值分别是 ,而你有一个容量为C的背包,请问如何求出所能拿的最大价值呢? 对于动态规划,我们先需要找到一条推导公式,然后确定边界: 我们设

    2024年02月07日
    浏览(16)
  • python数据结构与算法-动态规划(最长公共子序列)

    一个序列的子序列是在该序列中删去若干元素后得 到的序列。 例如:\\\"ABCD”和“BDF”都是“ABCDEFG”的子序列。 最长公共子序列(LCS) 问题: 给定两个序列X和Y,求X和Y长度最大的公共子字列。 例:X=\\\"ABBCBDE”Y=\\\"DBBCDB”LCS(XY)=\\\"BBCD\\\" 应用场景:字符串相似度比对 (1)问题思考 思考: 暴

    2024年02月08日
    浏览(12)
  • 【数据结构与算法】Kadane‘s算法(动态规划、最大子数组和)

    Kadane\\\'s 算法是一种用于解决最大子数组和问题的动态规划算法。这类问题的目标是在给定整数数组中找到一个连续的子数组,使其元素之和最大(数组含有负数)。 算法的核心思想是通过迭代数组的每个元素,维护两个变量来跟踪局部最优解和全局最优解。 以下是Kadane’s算

    2024年03月22日
    浏览(22)
  • ​Python—数据结构与算法​---动态规划—DP算法(Dynamic Programing)

    目录 我们一路奋战, 不是为了改变世界, 而是为了不让世界改变我们。 动态规划——DP算法(Dynamic Programing) 一、🏔斐波那契数列(递归VS动态规划) 1、🐒斐波那契数列——递归实现(python语言)——自顶向下 2、🐒斐波那契数列——动态规划实现(python语言)——自底

    2024年02月10日
    浏览(10)
  • 【零基础】学python数据结构与算法笔记14-动态规划

    学习python数据结构与算法,学习常用的算法, b站学习链接 动态规划在基因测序、基因比对、hmm 有应用场景。 从斐波那契数列看动态规划 练习: 使用递归和非递归的方法来求解斐波那契数列。 这种非递归求斐波那契数,可以看成是一个动态规划思想,每次都会把重复子问

    2023年04月09日
    浏览(7)
  • 【算法集训】基础数据结构:十、矩阵

    矩阵其实就是二维数组,这些题目在9日集训中已经做过,这里做的方法大致相同。

    2024年02月04日
    浏览(11)
  • 【数据结构与算法】三个经典案例带你了解动态规划

    从表中我们可以看到,最大的公共子串长度为2,一共有两个长度为2的公共子串,分别是第一个字符串的第2个字符到第3个字符和第一个字符串的第3个字符到第4个字符,即 ba 和 ac 根据上面的方法,我们来用代码封装一下求取最大公共子串的函数 function publicStr(s1, s2) { // 创建

    2024年04月09日
    浏览(14)
  • 算法与数据结构(二十三)动态规划设计:最长递增子序列

    注:此文只在个人总结 labuladong 动态规划框架,仅限于学习交流,版权归原作者所有; 也许有读者看了前文 动态规划详解,学会了动态规划的套路:找到了问题的「状态」,明确了 dp 数组/函数的含义,定义了 base case;但是不知道如何确定「选择」,也就是找不到状态转移

    2024年02月13日
    浏览(7)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包