算法:动态规划---斐波那契和最短路径

这篇具有很好参考价值的文章主要介绍了算法:动态规划---斐波那契和最短路径。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

从本篇开始总结的是动态规划的一些内容,动态规划是算法中非常重要的一个版块,因此也是学习算法中的一个重点,在学习动态规划前应当要把动态规划的基础知识学习一下

算法原理

动态规划既然是一个新的算法,这个名字也是新名字,那么就要首先明确这个算法的名字代表什么含义

动态规划是什么?
动态规划其实就是dp表中的值所表示的含义

那什么又是dp表?
dp表是解决这类问题中必须要使用的一个内容,通常是借助vector来表示

dp表怎么写出来?
一般来说题目要求中会有一些提示,同时在分析问题的过程中,如果遇到了分析的过程中有重复的子问题,也可以借助这个逻辑写出一个状态转移方程,利用这个状态转移方程就可以填写到dp表

状态转移方程
状态转移方程就是在动态规划中根据一部分提示找到dp表的填入方法,再根据这个方法就可以借助dp表解决问题,因此状态转移方程是解决问题的关键

斐波那契数列模型

首先用一个比较简单的题目来上手动态规划

第n个泰波那契数列

算法:动态规划---斐波那契和最短路径,# 算法,C++,算法,动态规划

对于这个题来说,可以用上面的动态规划的方法来处理:

首先创建一个dp表,再从题目中找到状态转移方程,再利用状态转移方程写入dp表,再利用dp表求出要找的数据

class Solution 
{
public:
    int tribonacci(int n) 
    {
        // 处理边界
        if(n==0)
        {
            return 0;
        }
        if(n==1 || n==2)
        {
            return 1;
        }
        // 创建dp表
        vector<int> dp(n+1);

        // 初始化dp表
        dp[0]=0;
        dp[1]=1;
        dp[2]=1;

        //填入dp表
        for(int i=3;i<=n;i++)
        {
            dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
        }

        // 返回值
        return dp[n];
    }
};

三步问题

算法:动态规划---斐波那契和最短路径,# 算法,C++,算法,动态规划

分析问题:

假设现在有1个台阶,那么小孩跳到这个台阶的方法有1种,直接从地面走到第一个台阶上

假设现在有2个台阶,那么小孩跳到这个台阶的方法有2种,第一种从地面直接走到第二个台阶上,第二种是小孩从地面走到第一个台阶,再从第一个台阶走到第二个台阶上

假设现在有3个台阶,那么小孩跳到这个台阶的方法有4种,第一种直接跳到第三个台阶上,第二种先跳到第一个台阶,再从第一个台阶向第三个台阶跳,而从第一个台阶向第三个台阶跳又有两种,参考有2个台阶的方案,那么总共第二种方法有2种,第三种小孩跳到第二个台阶,再从第二个台阶跳到第三个台阶,因此总共有四种方法

假设现在有4个台阶,那么小孩跳到第四个台阶的方法总共有7种,先让小孩走到第一个台阶,再从第一个台阶走到第四个台阶即可,而小孩走到第一个台阶的方法有1种;也可以先让小孩走到第二个台阶,再从第二个台阶走到第四个台阶,而小孩走到第二个台阶的方法有2种;先让小孩走到第三个台阶,再从第三个台阶直接到第四个台阶,而直接让小孩走到第四个台阶的方法有4种,因此上面的这些总计是7种

假设现在有5个台阶,那么小孩跳到第五个台阶的方法有13种,先让小孩跳到第二个台阶,再从第二个台阶直接到第五个台阶…

因此规律就找到了,其实就是一个斐波那契数列的变形问题,利用上面的例题的思路就可以解决这个问题

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

使用最小花费爬楼梯

算法:动态规划---斐波那契和最短路径,# 算法,C++,算法,动态规划
此题也是动态规划中的一个典型题,这里从两个角度来看这道题

从最开始的介绍中可以知道,对于动态规划的问题来说,关键是dp[i]的意义和状态转移方程,在解决问题的过程中要优先对这两个部分进行思考和解决,那么两个不同的dp[i]的角度来看这个题

首先从第一个角度来看:

如果这里的dp[i]表示的是,上到第i个台阶需要花费多少钱:
那么可以这样思考问题,要知道上到第i个台阶需要多少钱,就必然要知道上到第i-1个台阶要花多少钱,再用这个钱加上上第i-1个台阶要花多少钱,由于一次可以上两个台阶,因此也要知道上到第i-2个台阶需要多少钱和上这个台阶需要多少钱,再比较一下从第i-1个台阶上划算还是从第i-2个台阶上划算,比较后就可以得到dp[i]的值,因此状态转移方程就很容易得到了

dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])

此时注意一下边界初始化问题:在第0和第1个台阶是不需要花钱的,于是初始化为0即可,代码也可以很好的实现出来

class Solution 
{
public:
    int minCostClimbingStairs(vector<int>& cost) 
    {
        vector<int> dp(cost.size()+1);
        dp[0]=0;
        dp[1]=0;

        for(int i=2;i<=cost.size();i++)
        {
            dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }

        return dp[cost.size()];
    }
};

以上为第一种思考的方式,dp[i]对应的意义还有其他,这里还可以理解为从第i个位置上到最顶上需要的花费,因此这里也可以借助这个意义来解决

那如果要求从第i个台阶上到顶端要花多少钱,需要知道从第i个台阶一次上一个台阶还是一次上两个台阶比较划算,因此这里又需要知道i+1和i+2的值,根据这两个的值决定一次上一个台阶还是上两个台阶,因此状态转移方程也可以得出来了:

dp[i]=min(dp[i+1]+cost[i],dp[i+2]+cost[i]);

那么代码的实现也可以得出:

class Solution 
{
public:
    int minCostClimbingStairs(vector<int>& cost) 
    {
        int n=cost.size();
        vector<int> dp(n);
        dp[n-1]=cost[n-1];
        dp[n-2]=cost[n-2];

        for(int i=n-3;i>=0;i--)
        {
            dp[i]=min(dp[i+1]+cost[i],dp[i+2]+cost[i]);
        }

        return min(dp[0],dp[1]);
    }
};

解码方法

算法:动态规划---斐波那契和最短路径,# 算法,C++,算法,动态规划

class Solution 
{
public:
    int numDecodings(string s) 
    {
        // 处理特殊情况
        if(s[0] == '0')
            return 0;
        if(s.size() == 1)
            return 1;
        // 状态转移方程 dp[i] = dp[i - 1] + dp[i - 2]
        int n = s.size();
        vector<int> dp(n, 0);
        // 初始化问题
        if(s[0] >= '1' && s[0] <= '9')
            dp[0] = 1;
        else
            dp[0] = 0;

        if(s[1] >= '1' && s[1] <= '9')
            dp[1] += 1;
        int a = s[0] - '0', b = s[1] - '0';
        if((a * 10 + b) >= 10 && (a * 10 + b) <= 26)
            dp[1] += 1;
        
        for(int i = 2; i < n; i++)
        {
            if(s[i] >= '1' && s[i] <= '9')
                dp[i] += dp[i - 1];
            int a = s[i - 1] - '0', b = s[i] - '0';
            if(a * 10 + b >= 10 && a * 10 + b <= 26)
                dp[i] += dp[i - 2];
        }
        return dp[n - 1];
    }
};

路径问题

不同路径

算法:动态规划---斐波那契和最短路径,# 算法,C++,算法,动态规划

class Solution 
{
public:
    int uniquePaths(int m, int n) 
    {
        // 建表
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        // 状态转移方程 dp[i, j] = dp[i - 1, j] + dp[i, j - 1];
        // 填表
        dp[0][1] = 1;
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++)
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        return dp[m][n];
    }
};

不同路径II

算法:动态规划---斐波那契和最短路径,# 算法,C++,算法,动态规划

class Solution 
{
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) 
    {
        // 1.建表
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

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

        // 3.填表
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++)
                if(obstacleGrid[i - 1][j - 1] == 0)
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

        // 4.返回结果
        return dp[m][n];
    }
};

珠宝的最高价值

算法:动态规划---斐波那契和最短路径,# 算法,C++,算法,动态规划

class Solution 
{
public:
    int jewelleryValue(vector<vector<int>>& frame) 
    {
        // 状态转移方程:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1]
        // 1. 建表
        int m = frame.size(), n = frame[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

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

        // 3. 填表
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++)
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];

        // 4. 返回值
        return dp[m][n];
    }
};

地下城游戏

算法:动态规划---斐波那契和最短路径,# 算法,C++,算法,动态规划文章来源地址https://www.toymoban.com/news/detail-823815.html

class Solution 
{
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) 
    {
        int n = dungeon.size(), m = dungeon[0].size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MAX));
        dp[n][m - 1] = dp[n - 1][m] = 1;
        for (int i = n - 1; i >= 0; --i)
        {
            for (int j = m - 1; j >= 0; --j)
            {
                int minn = min(dp[i + 1][j], dp[i][j + 1]);
                dp[i][j] = max(minn - dungeon[i][j], 1);
            }
        }
        return dp[0][0];
    }
};

到了这里,关于算法:动态规划---斐波那契和最短路径的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 算法刷题Day 38 动态规划理论基础+斐波那契数+爬楼梯

    动态规划的解题步骤: 确定 dp 数组(dp table)以及下标的含义 确定递推公式 dp 数组如何初始化 确定遍历顺序 举例推导 dp 数组 很基础

    2024年02月15日
    浏览(53)
  • Java数据结构与算法:动态规划之斐波那契数列

    大家好,我是免费搭建查券返利机器人赚佣金就用微赚淘客系统3.0的小编。在这寒冷的季节里,让我们一同探讨Java中的动态规划,重点关注解决问题的经典代表之一——斐波那契数列。 动态规划简介 动态规划是一种解决问题的数学方法,通常用于优化递归算法。它通过将问

    2024年01月22日
    浏览(47)
  • 数据结构与算法之动态规划: Leetcode 509. 斐波那契数 (Typescript版)

    斐波那契数 https://leetcode.cn/problems/fibonacci-number/ 描述 斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: 给定 n ,请计算 F(n) 。 示例 1 示例 2 示例 3 提示 0 = n = 30 算法实现 1 )方案 1 这

    2024年02月04日
    浏览(43)
  • 算法Day38 | 动态规划,509. 斐波那契数, 70. 爬楼梯, 746. 使用最小花费爬楼梯

    动态规划是一种解决问题的算法思想。它通常用于优化问题,其中要求找到一个最优解或最大化(最小化)某个目标函数。 动态规划的核心思想是 将问题分解成更小的子问题,并通过存储子问题的解来避免重复计算 。这样,可以通过解决子问题来构建原始问题的解。动态规

    2024年02月09日
    浏览(57)
  • 动态规划-斐波那契数

    斐波那契数是一个很好的熟悉和理解动态规划的例子,通过斐波那契数可以更好的理解动态规划的精髓,动态规划是后面的计算是如何借助于前面的计算结果来加快计算速度的。 斐波那契数和斐波那契数列其实可以看成是一道题,只不过两题的限制性条件稍微有差别 斐波那

    2024年02月14日
    浏览(35)
  • 【动态规划】是泰波那契数,不是斐波那契数

    Problem: 1137. 第 N 个泰波那契数 首先我们来解读一下本题的意思🔍 相信读者在看到【泰波那契数】的时候,不禁会联想到【斐波那契数】,它们呢是一对孪生兄弟,这个 泰波那契数 相当于是 斐波那契数 的加强版 我们首先可以来看到这个递推公式 Tn+3 = Tn + Tn+1 + Tn+2 ,读者可

    2024年02月08日
    浏览(46)
  • 【动态规划】斐波那契数列模型

    冻龟算法系列之斐波那契数列模型 动态规划(英语:Dynamic programming,简称 DP) ,是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质

    2024年02月09日
    浏览(63)
  • 算法训练第三十八天|动态规划理论基础、509. 斐波那契数 、70. 爬楼梯 、 746. 使用最小花费爬楼梯

    参考:https://programmercarl.com/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html 动态规划是什么 动态规划,英文:Dynamic Programming,简称DP,如果某一问题有很多重叠子问题,使用动态规划是最有效的。 所以 动态规划中每一个状态一定是由上一个状态推导出来的 ,这一

    2024年02月04日
    浏览(39)
  • LeetCode 509 斐波那契数(动态规划)

     509. 斐波那契数 - 力扣(LeetCode)   斐波那契数  (通常用  F(n)  表示)形成的序列称为  斐波那契数列  。该数列由  0  和  1  开始,后面的每一项数字都是前面两项数字的和。也就是: 给定  n  ,请计算  F(n)  。 【思路】动态规划 动规五部曲: 1.确定dp数组以及下

    2024年02月07日
    浏览(53)
  • 动态规划02-斐波那契类型二

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

    2024年01月16日
    浏览(40)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包