C++算法第十一天

ops/2024/12/20 6:44:10/

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

第一题

题目链接

题目解析

代码原理

代码编写

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.ppmy.cn/ops/143406.html

相关文章

WebRTC搭建与应用(一)-ICE服务搭建

WebRTC搭建与应用(一) 近期由于项目需要在研究前端WebGL渲染转为云渲染&#xff0c;借此机会对WebRTC、ICE信令协议等有了初步了解&#xff0c;在此记录一下&#xff0c;以防遗忘。 第一章 ICE服务搭建 文章目录 WebRTC搭建与应用(一)前言一、ICE是什么&#xff1f;二、什么…

服务器数据恢复—RAIDZ离线硬盘数超过热备盘数导致阵列崩溃的数据恢复案例

服务器存储数据恢复环境&#xff1a; ZFS Storage 7320存储阵列中有32块硬盘。32块硬盘分为4组&#xff0c;每组8块硬盘&#xff0c;共组建了3组RAIDZ&#xff0c;每组raid都配置了热备盘。 服务器存储故障&#xff1a; 服务器存储运行过程中突然崩溃&#xff0c;排除人为误操…

游戏渠道假量解决方案

某推广公司在推广过程中被查出“短期内点击量激增”“存在同一地址多次访问”“已注册用户重复注册”等数据作弊行为&#xff0c;法院判罚退还服务费200余万元&#xff0c;并赔偿违约金约350万元。 某公司为提升其游戏在应用商店榜单排名&#xff0c;委托某网络公司进行下载、注…

循环神经网络(RNN)在时序预测中的应用与优势

目录 ​编辑 引言 RNN的基本结构与工作原理 RNN的记忆能力 参数共享与灵活性 动态特征提取 处理变长序列 序列到序列的学习 解决梯度消失和爆炸问题 端到端学习 RNN在实际应用中的优势 RNN的挑战与改进 结论 引言 在数据科学和机器学习领域&#xff0c;时序预测是…

使用 Python 实现 WebSocket 服务器与客户端通信

简介 WebSocket 是一种基于 TCP 协议的通信协议&#xff0c;能够在客户端与服务器之间进行全双工&#xff08;双向&#xff09;通信。相比传统的 HTTP 协议&#xff0c;WebSocket 可以实现实时数据的传输&#xff0c;尤其适合需要实时交互的应用场景&#xff0c;如在线游戏、实…

3D目标检测数据集及评价指标

1. KITTI 一个前视双目数据集&#xff0c;附有雷达数据&#xff0c;主要用于单目3D目标检测模型。数据集根据遮挡将目标分为三档&#xff0c;分别是未遮挡Easy&#xff0c;半遮挡Mod.&#xff0c;和大部分遮挡Hard&#xff0c;一般模型检测指标都是根据这三类标签分别计算mAP。…

HCIE-day7

三层路由 当路由器&#xff08;或者其他三层设备&#xff09;收到一个IP数据包时&#xff0c;路由器会找出报文中的IP头里的目的IP地址&#xff0c;然后根据目的IP地址在自己的路由表&#xff08;routing table&#xff09;中进行查询&#xff0c;找到匹配的路由条目之后&…

GIT区域介绍及码云+GIt配置仓库

GIT区域介绍 创建文件夹git init 1、git有3个区域 工作区&#xff08;working directory&#xff09;&#xff1a;项目的根目录&#xff0c;不包 括.git在内的其他文件暂存区&#xff08;stage area&#xff09;&#xff1a;是一个看不见的区域&#xff0c;git add 命令就是将文…