Dp solution in c (8msec)


  • 0

    int max_row;
    int max_col;
    int * dynamic;

    int find_health(int** dungeon, int r, int c) {
    int max_health = 0, health = 0, x;

    if (r == max_row - 1 && c == max_col-1 ) {
        return dungeon[r][c];
    }
    if (r < max_row -1) {
        if (dynamic[(r+1)*max_col+c] != 100)
        {
            max_health = dynamic[(r+1)*max_col+c];
          
        } else {
            max_health = find_health(dungeon, r+1, c);
            dynamic[(r+1)*max_col+c] = max_health;
            
        }
    }
    
    if (c < max_col -1) {
        if (dynamic[r*max_col+(c+1)] != 100)  {
            health = dynamic[r*max_col+(c+1)];
           
        } else {
            health = find_health(dungeon, r, c+1);
            dynamic[r*max_col+(c+1)] = health;
           
        }
    }
    
    if (c >= max_col-1) {
         ;
    } else if (r >= max_row-1)
        max_health = health;
    else if (max_health < health) {
        max_health = health;
    }
    x = dungeon[r][c] + (max_health > 0 ? 0 : max_health);
    
    return x;
    

    }

    int calculateMinimumHP(int** dungeon, int dungeonRowSize, int dungeonColSize) {
    int health = 0, n, i;
    max_row = dungeonRowSize;
    max_col = dungeonColSize;
    n = sizeof(int) * dungeonRowSize * dungeonColSize;
    dynamic = malloc(n);
    for (i=0;i< (n/sizeof(int)); i++) {
    *(dynamic+i) = 100;
    }

    health = find_health(dungeon, 0, 0);
    
    if (health >= 0)
        return 1;
    return ((health * -1)+1);
    

    }


Log in to reply
 

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