leetcode 174.地下城游戏

ops/2024/9/25 23:21:05/

思路:dp。

原先的时候其实是想这样用dfs的做法进行解答的,但是呢,是不对的。

这里作者dfs的思路是:首先找出来最小路径和,然后再处理最小路径和这条路径里面的初始值。但是,后来发现这样不一定是最优解,因为当我们的路径和并不是最小值的时候,也可能得到最小的初始值。官方案例上应该已经给出来实例了。

从左上到右下,dp[i][j]的意思就是:从起点到(i,j)的最小初始值多少。这样的话我们需要考虑两个问题:1.我们现在走的路径和是多少,是不是最优解?2.我们现在走到的这条路径和是不是最小初始值?这样的话我们需要考虑这种两个值,递推的不现实,上面也说了,如果顾及到前者,后者不一定是最优。所以我们需要换一种思路。

如果说我们正向推导不行,那么我们或许可以试一试反向推导。也就是说,我们从右下向左上进行推导。这给我们提供一种思路,就是正向推导行不通的时候我们可以试一试反向推导。

反向推的话,我们的dp就变成了:从(i,j)到终点的最低初始值。这样的话,我们就不需要顾及到路径和的问题了。因为我们现在已经在(i,j)这个坐标里面了,那么前面的路径和一定是不小于当前的最低初始值的,也就是说我们已经定下来了路径和一定是合理的,所以我们就相当于只考虑最低初始值的问题了。那么我们就只推它了。

我们也知道,我们站在这个位置有两条路可以选:一个就是向下走,一个就是向右走。那么我们需要知道,这两个路我们需要走哪个?当然是选择其中小的一个,因为我们求的是最低初始值。这样的话,我们需要初始化dp,这样的话,我们就需要为dp数组赋值一个很大的值以至于我们可以取到最小值。

那么,状态方程就出来了:dp[i][j]=max(1,min(dp[i+1][j],dp[i][j+1])-dungeon[i][j])。看右边这子,为什么需要-dungeon[i][j]?由于我们还并没有走到下一步,并且还需要考虑到当前的值。

另外,为什么要和1作比较呢?我们从题目中可以知道,骑士的初始值并不能<=0。所以我们的初始值最低是1,所以如果右边这个式子<=0,那么我们就自动给它赋值成1.

上代码:

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


http://www.ppmy.cn/ops/29496.html

相关文章

C++奇迹之旅:C++内存管理的机制初篇

文章目录 &#x1f4dd;C/C内存分布&#x1f320; C语言中动态内存管理方式&#x1f309;C内存管理方式 &#x1f320;new/delete操作内置类型&#x1f309;C与C链表构建对比 &#x1f6a9;总结 &#x1f4dd;C/C内存分布 这是C/C中程序内存区域划分图&#xff1a; 数据段&am…

基于php+mysql+html图书管理系统(含实训报告)

博主介绍&#xff1a; 大家好&#xff0c;本人精通Java、Python、Php、C#、C、C编程语言&#xff0c;同时也熟练掌握微信小程序、Android等技术&#xff0c;能够为大家提供全方位的技术支持和交流。 我有丰富的成品Java、Python、C#毕设项目经验&#xff0c;能够为学生提供各类…

速盾:cdn真的抗打吗?

CDN&#xff08;Content Delivery Network&#xff09;是一种分布式网络架构&#xff0c;旨在提供高速、可靠的内容传输服务。它通过将内容存储在位于全球各地的服务器上&#xff0c;使用户可以从最近的服务器获取内容&#xff0c;从而提高访问速度和性能。然而&#xff0c;尽管…

微信小程序demo-----制作文章专栏

前言&#xff1a;不管我们要做什么种类的小程序都涉及到宣传或者扩展其他业务&#xff0c;我们就可以制作一个文章专栏的页面&#xff0c;实现点击一个专栏跳转到相应的页面&#xff0c;页面可以有科普类的知识或者其他&#xff0c;然后页面下方可以自由发挥&#xff0c;添加联…

WPF之自定义绘图

1&#xff0c;创建自定义控件类 class CustomDrawnElement:FrameworkElement{public static readonly DependencyProperty BackgroundColorProperty;static CustomDrawnElement(){FrameworkPropertyMetadata meta new FrameworkPropertyMetadata(Colors.SkyBlue);meta.Affects…

C语言--贪吃蛇小游戏

目录 一、Win32API介绍 1.1Win32API 1.2控制台程序 1.3控制台屏幕上的坐标COORD 1.4GetStdHandle 1.5GetConsoleCursorInfo 1.6 CONSOLE_CURSOR_INFO 1.7 SetConsoleCursorInfo 1.8SetConsoleCursorPosition 1.9GetAsyncKeyState 二、贪吃蛇游戏设计与分析 2.1地图 …

小程序地理位置接口权限直接抄作业

小程序地理位置接口有什么功能&#xff1f; 随着小程序生态的发展&#xff0c;越来越多的小程序开发者会通过官方提供的自带接口来给用户提供便捷的服务。但是当涉及到地理位置接口时&#xff0c;却经常遇到申请驳回的问题&#xff0c;反复修改也无法通过&#xff0c;给的理由也…

JS 笔记9 认识JavaScript

相关内容&#xff1a;JS对象、属性、常用事件处理过程、运算符、if...else、for、…… <script type"text/javascript"></script> type属性用来指定MIME(Multipurpose Internet Mail Extension)类型&#xff0c;主要是告诉浏览器目前使用的是哪一种Scri…