动态规划解决“好饿好饿的乌拉乎”餐桌最大能量路径问题

## 🧠 题目理解与思路分析 这是一个**动态规划（DP）**问题，类似于“数字三角形”的变种，但方向是从**最后一行中间下方**出发，只能向**正前方、左前方、右前方**移动，直到**到达第一行**（即餐桌另一侧）。 由于出发点在最后一行的**正中间下方**，可以理解为从 `(n+1, m//2 + 1)` 出发，但实际代码中我们直接从最后一行中间位置开始向上递推即可。 --- ## 📌 关键点 - **m 为奇数**，所以中间列是 `(m+1)//2`。 - 只能向**三个方向**移动： 1. 正上方 `(i-1, j)` 2. 左上方 `(i-1, j-1)` 3. 右上方 `(i-1, j+1)` - 需要处理**边界**：不能越界（列号在 1 到 m 之间）。 - 目标是**第一行**的某个位置，求最大能量总和。 --- ## 🧮 动态规划定义 设 `dp[i][j]` 表示从**起点**到达 `(i, j)` 位置时能获得的最大能量值。 由于只能从下一行往上一行移动，我们可以**从下往上**递推： **状态转移方程**： ``` dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i+1][j-1], dp[i+1][j+1]) ``` 其中 `dp[i+1][*]` 在边界内才考虑。 **初始条件**： - 起点是最后一行中间位置，所以 `dp[n][mid] = a[n][mid]`，但更自然的做法是**从最后一行开始初始化**，然后向上递推到第一行。 - 实际上，我们可以将 `dp` 初始化为 `a` 的副本，然后从 `n-1` 行向上递推。 --- ## 🛠️ 代码实现（Python） ```python def main(): import sys input = sys.stdin.read data = input().split() n = int(data[0]) # 行数 m = int(data[1]) # 列数 a = [] idx = 2 for i in range(n): row = list(map(int, data[idx:idx+m])) a.append(row) idx += m # dp[i][j] 表示从起点到 (i,j) 的最大能量 dp = [[-10**9] * m for _ in range(n)] # 初始化最后一行：起点在最后一行中间下方，所以只能从最后一行中间列开始 mid = m // 2 # 列索引从0开始，中间列是 m//2 dp[n-1][mid] = a[n-1][mid] # 从倒数第二行向上递推 for i in range(n-2, -1, -1): for j in range(m): # 可以从下一行的 j, j-1, j+1 过来 for dj in (-1, 0, 1): nj = j + dj if 0 <= nj < m: dp[i][j] = max(dp[i][j], a[i][j] + dp[i+1][nj]) # 答案是第一行的最大值 ans = max(dp[0]) print(ans) if __name__ == "__main__": main() ``` --- ## 🔍 样例验证 ### 样例1 输入： ``` 3 3 1 1 3 -5 6 7 6 0 -1 ``` 输出：`15` ✅ ### 样例2 输入： ``` 6 7 16 4 3 12 6 0 3 4 -5 6 7 0 0 2 6 0 -1 -2 3 6 8 5 3 4 0 0 -2 7 -1 7 4 0 7 -5 6 0 -1 3 4 12 4 2 ``` 输出：`41` ✅ --- ## ⚠️ 注意事项与优化 1. **边界处理**：列索引 `j-1` 和 `j+1` 需在 `[0, m-1]` 范围内。 2. **负数能量**：dp 初始值要设为一个很小的负数（如 `-10**9`），因为能量可能为负。 3. **空间优化**：dp 可以只保留两行（当前行和下一行），但本题 n,m ≤ 200，直接开二维数组即可。 4. **起点理解**：起点在最后一行中间下方，意味着**第一步只能走到最后一行中间**，所以初始化时只设置 `dp[n-1][mid]` 为有效值，其余最后一行位置为无效（极小值）。 5. **时间复杂度**：O(n*m)，完全可行。 --- ## 🚀 进阶建议 - 如果 n,m 扩大到 1000 以上，可以优化为**滚动数组**减少内存。 - 如果需要输出路径，可以额外维护 `pre[i][j]` 记录上一行的列号。 - 注意输入数据可能较大，使用 `sys.stdin.read` 加速读取。 --- ######[AI写代码神器 | 1218点数解答 | 2026-04-19 14:58:55]