动态规划-扫地机器人最少初始电量

  扫地机器人在一个方格形状的地图中执行清扫任务，地图中每一个格子代表一个房间，地图用一个数组来表示：

• 1）扫地机器人从地图左上角出发，每次清扫完一个房间后只能向石或向下走到另外一个房间，最后到达右下角的房间完成清扫任务；
• 2）地图中每个房间的数字，负数表示清扫房间需要消耗的电量，非负数表示该房间有充电设备，可以在该房间充电获得的电量；
• 3）扫地机器人清扫过程中，走出任何一个房间，电量都不能小于1。为了保证扫地机器人能完成最右下角的房间的清扫任务并走出房间，初始电量至少是多少？
    根据输入的地图，输出扫地机器人的初始电量。

• 输入

3 3
-2-3 3
-5-10 1
0 30 -5
1
2
3
4

输出

7
1

解答：

#include 
using namespace std;
/*
3 3
-2 -3 3
-5 -10 1
0 30 -5
*/
int n, m;

int main(int argc, char** argv) {
  cin >> n >> m;
  vector<vector<int>> rooms(n, vector<int>(m));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> rooms[i][j];
    }
  }
  // dp[i][j] 代表机器人运动到[i][j]时，可以支撑它走完全程的当前电池电量的最小值
  // max 函数限制最小值
  vector<vector<int>> dp(n + 1, vector<int>(m + 1));
  dp[n - 1][m - 1] = max(1, -rooms[n - 1][m - 1] + 1);
  for (int i = n - 2; i >= 0; i--) {
    dp[i][m - 1] = dp[i + 1][m - 1] - rooms[i][m - 1];
    dp[i][m - 1] = max(1, dp[i][m - 1]);
  }
  for (int j = m - 2; j >= 0; j--) {
    dp[n - 1][j] = dp[n - 1][j + 1] - rooms[n - 1][j];
    dp[n - 1][j] = max(1, dp[n - 1][j]);
  }
  for (int i = n - 2; i >= 0; i--) {
    for (int j = m - 2; j >= 0; j--) {
      dp[i][j] = min(dp[i + 1][j] - rooms[i][j], dp[i][j + 1] - rooms[i][j]);
      dp[i][j] = max(1, dp[i][j]);
    }
  }
  cout << dp[0][0];
  return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40