# Shortest DP solution in 7 lines, with O(mn) space + O(n) time (C++)

• The idea is to:

A. calculate the required HP backward;

B. think negative points as "Debts" which needs to be add our required HP, meanwhile bonus points as "Payment" made to the debts;

C. reset HP value to 1 as soon as we "clear" our debts.

Here is the code

``````int calculateMinimumHP(vector<vector<int> > &b) {
int m = b.size(), n = b[0].size();
vector<int> hp(n+1, INT_MAX);

hp[n] = 1;
for (int i = m-1; i >= 0; i--) {
for (int j = n-1; j >= 0; j--) {
int t = min(hp[j], (i != m-1 && j == n-1) ? INT_MAX : hp[j+1]);
hp[j] = (t - b[i][j] <= 0) ? 1 :  t - b[i][j];
}
}

return hp[0];
}
``````

Obviously, the code means

1. Init a DP array to be count of the board's column;

2. Looping through N iteration and for each column j:

a. hp[j] = min(hp[j], hp[j+1]) - b[i][j], when the required hp[j] is greater than the cell value

b. hp[j] = 1, when the required hp[j] is less than the cell value, meaning that we have residual bonus points

• This is O(mn) time, the same as solutions from others posted here.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.