当前位置: 首页 > news >正文

C++算法第十一天

本篇文章我们继续学习动态规划

目录

第一题

题目链接

题目解析

代码原理

代码编写

第二题

题目链接

题目解析

代码原理

代码编写

第三题

题目链接

题目解析

代码原理

代码编写

第四题

题目链接

题目解析

代码原理

代码编写

第五题

题目链接

题目解析

代码原理

代码编写

题后总结


第一题

题目链接

题目解析

代码原理

代码编写

class Solution {

public:

    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {

        int m = obstacleGrid.size(), n = obstacleGrid[0].size();

        //建表

        vector<vector<int>> dp(m + 1, vector<int>(n + 1));

        //初始化

        dp[0][1] = 1;//当然这里dp[1][0] = 1也是可以的

        //填表

        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];

            }

        }

        return dp[m][n];

    }

};

第二题

题目链接

LCR 166. 珠宝的最高价值 - 力扣(LeetCode)

题目解析

代码原理

代码编写

class Solution {

public:

    int jewelleryValue(vector<vector<int>>& frame) {

        int m = frame.size(), n = frame[0].size();

        //建表

        vector<vector<int>> dp(m + 1, vector<int>(n + 1));

        //初始化

        dp[0][1] = 0;

        //填表

        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];

            }

        }

        return dp[m][n];

    }

};

第三题

题目链接

931. 下降路径最小和 - 力扣(LeetCode)

题目解析

代码原理

代码编写

class Solution {

public:

    int minFallingPathSum(vector<vector<int>>& matrix) {

        int n = matrix.size();

        //建表

        vector<vector<int>> dp(n + 1,vector<int>(n + 2, INT_MAX));

        //初始化第一行

        for(int j = 0; j < n + 2; j++)

        {

            dp[0][j] = 0;

        }

        //填表

        for(int i = 1; i < n + 1; i++)

        {

            for(int j = 1; j <= n; j++)

            {

                dp[i][j] = min(min(dp[i - 1][j - 1], dp[i - 1][j]),dp[i - 1][j + 1]) + matrix[i - 1][j - 1];

            }

        }

        int ret = INT_MAX;

        for(int j = 1; j <= n; j++)

        {

            ret = min(ret, dp[n][j]);

        }

        return ret;

    }

};

第四题

题目链接

64. 最小路径和 - 力扣(LeetCode)

题目解析

代码原理

代码编写

class Solution {

public:

    int minPathSum(vector<vector<int>>& grid) {

        int m = grid.size(), n = grid[0].size();

        //建表

        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));

        //初始化

        dp[0][1] = 0;

        //填表

        for(int i = 1; i <= m; i++)

        {

            for(int j = 1; j <= n; j++)

            {

                dp[i][j] = min(dp[i - 1][j],dp[i][j - 1]) + grid[i - 1][j - 1];

            }

        }

        return dp[m][n];

    }

};

第五题

题目链接

174. 地下城游戏 - 力扣(LeetCode)

题目解析

代码原理

这里的状态方程有个小错误需要注意一下,正确的我放在下面啦,别看漏哦

正确的状态转移方程:dp[i][j] = min(dp[i][j + 1],dp[i + 1][j]) - cur[i][j]

代码编写

class Solution {

public:

    int calculateMinimumHP(vector<vector<int>>& dungeon) {

        int m = dungeon.size(),n = dungeon[0].size();

        //建表

        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));

        //初始化

        dp[m][n - 1] = dp[m - 1][n] = 1;

        //填表

        for(int i = m - 1; i >= 0; i--)

        {

            for(int j = n - 1; j >= 0; j--)

            {

                dp[i][j] = min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j];

                dp[i][j] = max(1,dp[i][j]);

            }

        }

        return dp[0][0];

    }

};

题后总结

通过今天的题,我们可以总结出以下几点

1.填表时需要使用原表上的数据时,行列各减1

2.初始化部分的目的:保证填表时不越界

                                  保证填表时后面的数据正确

3.如何正确初始化:结合状态表示和状态转移方程,进行分析哪些地方存在越界的可能性

那么本篇文章的内容就先到此结束,我们下期文章再见!!!

记得一键三联哦

http://www.lryc.cn/news/506400.html

相关文章:

  • 常 用 类
  • ACL(访问控制列表)
  • json字符串转json
  • GPT-Omni 与 Mini-Omni2:创新与性能的结合
  • 探秘 JSON:数据交互的轻盈使者
  • 源码分析之Openlayers中的Attribution属性控件
  • Shell自定义(二)
  • 自然语言处理:我的学习心得与笔记
  • Oracle 中什么情况下 可以使用 EXISTS 替代 IN 提高查询效率
  • Spring基础分析08-集成JPA/Hibernate进行ORM操作
  • MySQL知识汇总(一)
  • PDFMathTranslate 一个基于AI优秀的PDF论文翻译工具
  • React+Vite从零搭建项目及配置详解
  • @pytest.fixture() 跟 @pytest.fixture有区别吗?
  • Google Cloud Architect 认证考试错题集5
  • 【Maven】基础(一)
  • 多模态抽取图片信息的 Prompt
  • WPF 使用LibVLCSharp.WPF实现视频播放、停止、暂停功能
  • Java全栈项目 - 校园招聘信息平台
  • java导出
  • 【嵌入式系统】期末试题库,ARM处理器,CortexM3内核,USART,EXTI,GPIO
  • arcgisPro相接多个面要素转出为完整独立线要素
  • QTday1
  • SAP ALV选择列排序时弹出定义排序顺序窗口问题
  • CSS Backgrounds(背景)
  • 欧拉计划 Project Euler 27 题解
  • 迁移学习--fasttext概述
  • 【数字信号处理】数字信号处理试题及答案,离散序列,Z变换,傅里叶变换
  • CNN、RNN、LSTM和Transformer之间的区别和联系
  • springboot448教学辅助系统(论文+源码)_kaic