1. Title Description

Difficult difficult

Some demons captured the princess (P) and locked her in the lower right corner of the dungeon. Dungeons are two-dimensional grids of M x N rooms. Our heroic knight (K), originally placed in the upper left room, must traverse the dungeon and save the princess by fighting demons.

The knight’s initial health point is a positive integer. If his health point drops to zero or below at any point, he dies immediately.

Some rooms are guarded by demons, so the knight loses health points when entering these rooms (if the value in the room is a negative integer, the knight loses health points); The other rooms are either empty (the value in the room is 0) or contain orbs that increase the knight’s health points (if the value in the room is a positive integer, the knight will increase his health points).

In order to reach the princess as quickly as possible, the knight decided to move only one step to the right or down at a time. Write a function to calculate the minimum initial health points needed to ensure that the knight can save the princess.

For example, considering the following layout of dungeons, if the knight follows the best path right -> right -> down -> down, the knight’s initial health point is at least 7.

Description:

There is no upper limit to how many health points a knight can earn.

Any room can be a threat to or increase the knight’s health points, including the upper left room where the knight enters and the lower right room where the princess is imprisoned.

Second, train of thought analysis

Key information:

  • If his health point drops to zero or below at any point, he dies immediately; The knight must have at least one health point in each room

  • The knight decided to move only one step to the right or down at a time; So there are two directions, right or down

  • Make sure the knight has the minimum initial health points required to save the princess. Find a minimum that works

If you go backwards, because you don’t know what’s going to happen, you’re going to have to update the previous value every time you go forward, and that’s going to be a lot of work, so it’s better to go backwards. So from the back to the front, each room has an optimal solution, and it’s going to be the optimal solution at the beginning, so that’s dynamic programming. Then do it!

Dynamic programming inverse process:

Make sure to enter the Princess’s room (2, 2) with 1 health point left, that is 1 – (-5) = 6;

If the knight enters the Princess’s room from the upper room (1, 2), the number of points required to enter (1, 2) is 6-1 = 5;

If the knight enters from the left room (2, 1), the number of points required to enter (2, 1) is 6-30 = -24, and the number of health points required to enter (2, 1) is greater than or equal to 1, so math. Max (1, -24) = 1;

If the knight enters the room (1, 1), choosing to go right takes 6 – (-10) = 16; To go down, 1 – (-10) = 11; Math.min(6 – (-10), 1 – (-10)); math.min (6, 1) – (-10); math.min (6, 1) – (-10); math.min (6, 1) – (-10); Math.max(1, math.min (6, 1) – (-10)); The minimum number of points to enter room (1, 1) is 11;

Formula is from the concrete to the abstract Math. Max (1, Math. Min (dp [j + 1], [I] dp [I + 1] [j]) – dungeon [I] [j])

Math.max(1, math.min (6, x) – (3)), math.max (1, math.min (6, x) – (3)), math.max (1, math.min (6, x) – (3)), math.max (1, math.min (6, x) – (3)) Math.min(6, x) is a minimum value that you can only go down to, and it gives you a value of 6, so if I give x a value greater than 6, I can use this formula. So how do we make sure that x is the largest? There is a maximum value in Number, which I just learned: number.max_value;

And then to make this formula work, we can add one more column on the right, one more row on the bottom; The values inside are number.max_value;

At this point, try using the formula to derive the minimum number of points per room:

Oh, how come all the values are maxima? Oh, oh, it’s a value that can be determined at the beginning, which value can be determined at the beginning? Naturally, the princess is in the room, that is, the princess is in the room to the right and down the room we virtual added, set the room to 1.

A fierce operation such as tiger, can be said to be very careful

AC code

var calculateMinimumHP = function (dungeon) {
  let m = dungeon.length;
  if (m == 0) return 0;
  let n = dungeon[0].length;
  let max = Number.MAX_VALUE;
  // Create a two-dimensional array, fill each value with the maximum value (min fill the maximum value, Max fill 0 or min)
  let dp = Array.from(m + 1); // Add one more line
  for (let i = 0; i <= m; i++) {
    dp[i] = [];
    for (let j = 0; j <= n; j++) { dp[i].push(max); }}// The last dp[I][j] the right and down ones should have 1
  dp[m][n - 1] = 1;
  dp[m - 1][n] = 1;
  // Where does the princess run back to the starting point
  for (let i = m - 1; i >= 0; i--) {
    for (let j = n - 1; j >= 0; j--) {
      let temp = Math.min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j];
      dp[i][j] = Math.max(1, temp); }}// console.log(dp)
  return dp[0] [0];
};
Copy the code

Four,

It’s not hard to write code, just give it a try; However, the process of train of thought analysis is very abrasive, I hope you can understand! This article is participating in the activity to brush the question punching task, let’s exchange!