Leetcode#174 Dungeon Game
2024-10-13 13:39:22
典型的地图寻路问题
如何计算当前位置最少需要多少体力呢?无非就是在向下走或向右走两个方案里做出选择罢了。
如果向下走,看看当前位置能提供多少体力(如果是恶魔就是负数,如果是草药就是正数),如果当前位置能够提供的体力比向下走所需要的最小体力还多,那么当前位置只需要1的体力就够了;否则,计算出额外需要多少体力。
如果向右走,同理。
设任意坐标(i, j)处最少需要health[i][j]的体力才能通关,则有如下递推公式:
health[i][j] = min{
dungeon[i][j] >= health[i+1][j] ? 1 : health[i+1][j] - dungeon[i][j],
dungeon[i][j] >= health[i][j+1] ? 1 : health[i][j+1] - dungeon[i][j]
}
因为递推公式只用到了相邻层,所以可以在编码时压缩成1维数组节省空间。
代码:
int calculateMinimumHP(vector<vector<int> > &dungeon) {
if (dungeon.empty() || dungeon[].empty()) return -; int m = dungeon.size();
int n = dungeon[].size();
vector<int> health(n, ); health[n - ] = dungeon[m - ][n - ] >= ? : - dungeon[m - ][n - ]; for (int j = n - ; j >= ; j--)
health[j] = dungeon[m - ][j] >= health[j + ] ? : health[j + ] - dungeon[m - ][j]; for (int i = m - ; i >= ; i--) {
health[n - ] = dungeon[i][n - ] >= health[n - ] ? : health[n - ] - dungeon[i][n - ];
for (int j = n - ; j >= ; j--) {
int right = dungeon[i][j] >= health[j + ] ? : health[j + ] - dungeon[i][j];
int down = dungeon[i][j] >= health[j] ? : health[j] - dungeon[i][j];
health[j] = min(right, down);
}
} return health[];
}
最新文章
- Oracle 的基本操作符
- .net实现webservice简单实例分享
- 据说每个大牛、小牛都应该有自己的库——Ajax
- Eclipse中Program arguments和VM arguments的说明
- android 比较靠谱的图片压缩
- ADO.NET笔记——SQL注入攻击
- 需要保存数据zabbix,不需要保存数据nagios
- chrome浏览器更新到chrome 29.0.1547.76 m,多出一些蛋疼的功能来。
- Java学习日记-2.5 关于0和无穷
- jQuery之文档处理
- es6 模板字变量和字符串占位符
- Mybatis注解和配置文件命名规范所引发的问题
- 10分钟让你的代码更加pythonic
- ATM Mechine (概率DP)
- JsonLayout log4j2 json格式输出日志
- 利用JavaCSV API来读写csv文件
- python类的__slots__属性、__del__属性、上下文(__enter__和__exit__)、
- 2.13 C++拷贝构造函数
- [UE4]透明按钮
- poj 2531 搜索剪枝
热门文章
- sail.js学习 - 安装篇
- php输出函数 var_dump, dump,print,print_r 区别
- 用开源中国(oschina)Git管理代码(整合IntelliJ 13.1.5)
- WIN8+VS2013编写发布WCF之三(调用)
- 实战Django:官方实例Part1
- Effective C# 学习笔记(原则二:为你的常量选择readonly而不是const)
- .NET开源工作流RoadFlow-系统布署中常见错误及处理方法
- MongoDB仲裁节点的理解以及memcached,zookeeper,redis,故障恢复方案思考.
- 【Javascript】: for循环中定义的变量在for循环体外也有效
- Android动画解析--XML