题解 | 走格子游戏

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minInitialPower(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        
        // dp[i][j] 表示从(i,j)到终点所需的最小行动力
        vector<vector<int>> dp(m, vector<int>(n, INT_MAX));
        
        // 初始化终点
        dp[m-1][n-1] = grid[m-1][n-1] <= 0 ? -grid[m-1][n-1] + 1 : 1;
        
        // 从终点反向计算
        for (int i = m-1; i >= 0; i--) {
            for (int j = n-1; j >= 0; j--) {
                if (i == m-1 && j == n-1) continue;
                
                int minPower = INT_MAX;
                
                // 向右移动
                if (j < n-1) {
                    minPower = min(minPower, dp[i][j+1]);
                }
                
                // 向下移动
                if (i < m-1) {
                    minPower = min(minPower, dp[i+1][j]);
                }
                
                // 计算当前格子所需的最小行动力
                if (minPower != INT_MAX) {
                    dp[i][j] = max(1, minPower - grid[i][j]);
                }
            }
        }
        
        return dp[0][0];
    }
};

int main() {
    int m, n;
    cin >> m >> n;
    
    vector<vector<int>> grid(m, vector<int>(n));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> grid[i][j];
        }
    }
    
    Solution solution;
    cout << solution.minInitialPower(grid) << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    static class Solution {
        public int minInitialPower(int[][] grid) {
            int m = grid.length;
            int n = grid[0].length;
            
            // dp[i][j] 表示从(i,j)到终点所需的最小行动力
            int[][] dp = new int[m][n];
            for (int[] row : dp) {
                Arrays.fill(row, Integer.MAX_VALUE);
            }
            
            // 初始化终点
            dp[m-1][n-1] = grid[m-1][n-1] <= 0 ? -grid[m-1][n-1] + 1 : 1;
            
            // 从终点反向计算
            for (int i = m-1; i >= 0; i--) {
                for (int j = n-1; j >= 0; j--) {
                    if (i == m-1 && j == n-1) continue;
                    
                    int minPower = Integer.MAX_VALUE;
                    
                    // 向右移动
                    if (j < n-1) {
                        minPower = Math.min(minPower, dp[i][j+1]);
                    }
                    
                    // 向下移动
                    if (i < m-1) {
                        minPower = Math.min(minPower, dp[i+1][j]);
                    }
                    
                    // 计算当前格子所需的最小行动力
                    if (minPower != Integer.MAX_VALUE) {
                        dp[i][j] = Math.max(1, minPower - grid[i][j]);
                    }
                }
            }
            
            return dp[0][0];
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        
        int[][] grid = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                grid[i][j] = sc.nextInt();
            }
        }
        
        Solution solution = new Solution();
        System.out.println(solution.minInitialPower(grid));
        
        sc.close();
    }
}

class Solution:
    def min_initial_power(self, grid: list) -> int:
        m, n = len(grid), len(grid[0])
        
        # dp[i][j] 表示从(i,j)到终点所需的最小行动力
        dp = [[float('inf')] * n for _ in range(m)]
        
        # 初始化终点
        dp[m-1][n-1] = -grid[m-1][n-1] + 1 if grid[m-1][n-1] <= 0 else 1
        
        # 从终点反向计算
        for i in range(m-1, -1, -1):
            for j in range(n-1, -1, -1):
                if i == m-1 and j == n-1:
                    continue
                
                min_power = float('inf')
                
                # 向右移动
                if j < n-1:
                    min_power = min(min_power, dp[i][j+1])
                
                # 向下移动
                if i < m-1:
                    min_power = min(min_power, dp[i+1][j])
                
                # 计算当前格子所需的最小行动力
                if min_power != float('inf'):
                    dp[i][j] = max(1, min_power - grid[i][j])
        
        return dp[0][0]

# 读取输入
m, n = map(int, input().split())
grid = []
for _ in range(m):
    row = list(map(int, input().split()))
    grid.append(row)

solution = Solution()
print(solution.min_initial_power(grid))