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

  • 2

    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

  • 0

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

Log in to reply

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