Recursive DP solution


  • 0
    H

    int min_health(int r, int c){
    if (r >= R || c >= C) return INT_MIN;
    if (r == R-1 && c == C-1) {
    return arr[r][c];
    }

    if(cache[r][c] != -1) return cache[r][c];
    
    /* From this location (r,c) find best/max health possible */
    int h = max (min_health(r+1, c),  // Rightwards
                 min_health(r, c+1)); // Downwards
    
    /* Return worst health with/without current cell value*/
    int res = min(h+arr[r][c], arr[r][c]);
    cache[r][c] = res;
    
    return res;
    

    }

    int calculate_min_health() {
    int h = min_health(0,0);
    return (h >=0) ? 1 : (h * -1) +1;
    }


Log in to reply
 

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