笔试时间：2024年08月11日 仅有一道编程题

历史笔试传送门：2023秋招笔试合集

第一题

题目：无人机的最低初始电量

在一个m*n的二维网格中，我们的无人机从左上角出发去到右下角。无人机初始电量是一个正整数，如果电量降低到0或以下，那么会立即炸机坠毁。路上经过的所有网格有不同的物理特性，导致无人机经过时消耗的电量不一样（负整数代表消耗的电量值）；有些网格如此奇妙，对于无人机来说如同瞬间通过不消耗电量（网格数值为0）；还有一些网格无人机经过会增加电量（正整数代表增加的电量）；

为了尽快到达右下角，无人机每次只向右或向下移动一步。请编程计算并返回能够确保无人机到达右下角的最低初始电量。

输入描述

输入为整数的二维数组。

输出描述

输出为正整数。

样例输入一

3 3

-2 -3 3

-5 -10 1

10 30 -5

样例输出一

7

提示

m == grid.length

n == grid[i].length

m>=1,n<=200

-1000 <= grid[i][j] <=1000

参考题解

经典的网格迷宫DP问题。设 dp[i][j] 表示从位置 (i, j) 到达终点所需的最低初始电量。右下角位置 (m-1, n-1) 的最低初始电量为 max(1, 1 - grid[m-1][n-1])。这里 1 是因为最低电量不能低于 1。对于每个位置 (i, j)，你需要考虑从该位置向右或向下走的最低电量，并选择其中较小的那个。递推关系为：dp[i][j]=max(1,min(dp[i+1][j],dp[i][j+1])−grid[i][j])

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <numeric>
#include <limits>
#include <climits>  

using namespace std;

class Solution {
public:

/* Write Code Here */
int calcMinimumPower(vector < vector < int > > grid) {
    int m = grid.size();
    int n = grid[0].size();
    vector<vector<int>> dp(m, vector<int>(n, INT_MAX));

    dp[m-1][n-1] = max(1, 1 - grid[m-1][n-1]);

    for (int i = m - 1; i >= 0; --i) {
        for (int j = n - 1; j >= 0; --j) {
            if (i < m - 1) {
                dp[i][j] = min(dp[i][j], max(1, dp[i + 1][j] - grid[i][j]));
            }
            if (j < n - 1) {
                dp[i][j] = min(dp[i][j], max(1, dp[i][j + 1] - grid[i][j]));
            }
        }
    }

    return dp[0][0];
}
};
int main() {
    int res;

    int grid_rows = 0;
    int grid_cols = 0;
    cin >> grid_rows >> grid_cols;
    vector< vector < int > > grid(grid_rows);
    for(int grid_i=0; grid_i<grid_rows; grid_i++) {
        for(int grid_j=0; grid_j<grid_cols; grid_j++) {
            int grid_tmp;
            cin >> grid_tmp;