💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

🍥 有很多套卷，每套卷子有 0/1/2 道编程题，题目内容不一定相同，这样 选择题、填空、问答 的比重就占很大了。

🍉 本题是力扣的一道原题，虽然比较经典，但对第一次接触的小伙伴来说还是有一定难度的。

🏺 01.LYA的宝藏探险

问题描述

LYA是一位著名的探险家，她最近发现了一个古老的宝藏地图。这张地图显示了一个 的矩形区域，每个格子都有特殊的能量场。LYA需要从左上角出发，到达右下角才能获得宝藏。

地图上的每个格子都有一个整数值，代表不同的能量场强度：

• 负数表示该格子会消耗LYA的能量
• 正数表示该格子会补充LYA的能量
• 零表示该格子对LYA的能量没有影响

LYA每次只能向右或向下移动一格。如果她的能量在任何时候降到零或以下，她就会被传送出地图，探险失败。

为了确保探险成功，LYA需要计算出最低的初始能量值。请你帮助LYA计算这个最低初始能量值，使她能够安全地到达右下角的宝藏位置。

输入格式

第一行包含两个正整数 和 ，分别表示地图的行数和列数。

接下来的 行，每行包含 个整数，表示地图上每个格子的能量场强度。

输出格式

输出一个正整数，表示LYA需要的最低初始能量值。

样例输入

3 3
-2 -3 3
-5 -10 1
10 30 -5

样例输出

7

数据范围

题解

力扣原题改编：174. 地下城游戏

这个问题可以使用动态规划来解决。我们可以从右下角开始，逆向计算到达每个格子所需的最低能量。

定义 为从格子 到达右下角所需的最低能量。我们可以得到以下状态转移方程：

这个方程的含义是：

1. 我们取右边和下边格子所需能量的最小值
2. 减去当前格子的能量值
3. 确保结果至少为1（因为能量不能为负）

最终， 就是我们需要的答案。

参考代码

• Python

def min_initial_energy(grid):
    m, n = len(grid), len(grid[0])
    # 初始化dp数组，设置一个较大的初始值
    dp = [[float('inf')] * (n + 1) for _ in range(m + 1)]
    
    # 设置边界条件
    dp[m][n-1] = dp[m-1][n] = 1
    
    # 从右下角开始填充dp数组
    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            # 计算当前格子所需的最低能量
            min_energy = min(dp[i+1][j], dp[i][j+1])
            dp[i][j] = max(1, min_energy - grid[i][j])
    
    return dp[0][0]

# 读取输入
m, n = map(int, input().split())
grid = [list(map(int, input().spl