Simple DP solution in Java


  • 85
    Y

    only need to store one killed enemies value for a row and an array of each column;
    if current grid value is W, this means previous stored value becomes invalid, you need to recalculate.

     public int maxKilledEnemies(char[][] grid) {
        if(grid == null || grid.length == 0 ||  grid[0].length == 0) return 0;
        int max = 0;
        int row = 0;
        int[] col = new int[grid[0].length];
        for(int i = 0; i<grid.length; i++){
            for(int j = 0; j<grid[0].length;j++){
                if(grid[i][j] == 'W') continue;
                if(j == 0 || grid[i][j-1] == 'W'){
                     row = killedEnemiesRow(grid, i, j);
                }
                if(i == 0 || grid[i-1][j] == 'W'){
                     col[j] = killedEnemiesCol(grid,i,j);
                }
                if(grid[i][j] == '0'){
                    max = (row + col[j] > max) ? row + col[j] : max;
                }
            }
    
        }
        
        return max;
    }
    
    //calculate killed enemies for row i from column j
    private int killedEnemiesRow(char[][] grid, int i, int j){
        int num = 0;
        while(j <= grid[0].length-1 && grid[i][j] != 'W'){
            if(grid[i][j] == 'E') num++;
            j++;
        }
        return num;
    }
    //calculate killed enemies for  column j from row i
    private int killedEnemiesCol(char[][] grid, int i, int j){
        int num = 0;
        while(i <= grid.length -1 && grid[i][j] != 'W'){
            if(grid[i][j] == 'E') num++;
            i++;
        }
        return num;
    }

  • 0
    W

    Have same idea, thanks for sharing your code. Clean! Up voted.


  • 1
    Y

    @willcomeback thank you


  • 0
    W
    This post is deleted!

  • 6
    Q

    Thank you for your solution, your solution can surely work. However, my question will be "Is this solution really using DP ideas to solve it? I am afraid it is not. Please correct me if I am wrong. Thank you.


  • 0
    L

    @Yun.Hu
    A very clear and easy to understand solution. Thanks!


  • 1
    A

    @Yun.Hu What is the running time for this solution?


  • 0
    L

    Dear! please post running time of the solution!


  • 0
    C

    @acheiver It is O(m*n)


  • 0

    @acheiver I think it is O(m * n). Although there is another for loop k inside for loops of i and j. It just calculates the enemies in advance. In the end, it will traverse this grid once to compute the enemies that are killed. If someone found me wrong, please point your view.


  • 1
    C

    @qian23 I think it is. It reuses previous results.


  • 0

    @qian23 it is little a DP-like SOLUTION, the only place col[], which is storing col enemies count, is only updated once for consecutive enemies column, and reused for later calculation (when there is '0', where bomb can be planted)


  • 0
    W

    No one found the error? It inverse the row and col conception.

    said in Simple DP solution in Java:

    //calculate killed enemies for row i from column j
    private int killedEnemiesRow(char[][] grid, int i, int j){
    int num = 0;
    while(j <= grid[0].length-1 && grid[i][j] != 'W'){
    if(grid[i][j] == 'E') num++;
    j++;
    }
    return num;
    }
    //calculate killed enemies for column j from row i
    private int killedEnemiesCol(char[][] grid, int i, int j){
    int num = 0;
    while(i <= grid.length -1 && grid[i][j] != 'W'){
    if(grid[i][j] == 'E') num++;
    i++;
    }
    return num;


  • 0
    L

    @qian23 I think it is, imagine if we use DP without optimization, colMatrix = int[grid.length][grid[0].length], f(i, j) represents for point(i, j), how many enemies we can kill in col j, and if point(i, j) is not a wall, we can reuse this result as previous result into point(i + 1, j) and so on. the same with rowMatrix.

    The solution optimized based on this using a int[] col(e.g. i = 5, for col[j], it stores col[i] = colMatrix[4][j], which is the col result for row i - 1.).
    "row" stores previous row result, e.g. for poin(i, j), row represents how many enemies can be killed in row i, and when there is a wall, this value need to be recalculated.


  • 0
    L

    @wzrthhj I think he/she is right, hope my reply right after you help.


  • 19

    This question is actually very simple. Do not need any fancy. Just travel each column twice: from left and from right; then travel each row twice: from top and from bottom. My code beats 90%.

    public class Solution {
        public int maxKilledEnemies(char[][] grid) {
            if(grid== null || grid.length == 0 || grid[0].length==0) return 0; 
            int rows = grid.length; 
            int cols = grid[0].length; 
            int max = 0; 
            int[][] dp = new int[rows][cols];
            //travel each column twice: from left and from right
            for(int i = 0; i<rows; i++){
                int cnt = 0; 
                for(int k = 0; k<cols; k++){
                    if(grid[i][k]=='0'){
                        dp[i][k] = cnt; 
                    }else if(grid[i][k]=='E'){
                        cnt++;
                    }else{
                        cnt = 0; 
                    }
                }
                cnt = 0; 
                for(int k = cols-1; k>=0; k--){
                    if(grid[i][k]=='0'){
                        dp[i][k] += cnt; 
                    }else if(grid[i][k]=='E'){
                        cnt++;
                    }else{
                        cnt = 0;
                    }
                }
            }
            //travel each row twice: from top and from bottom
            for(int i = 0; i<cols; i++){
                int cnt = 0; 
                for(int k = 0; k<rows; k++){
                    if(grid[k][i]=='0'){
                        dp[k][i] += cnt; 
                    }else if(grid[k][i]=='E'){
                        cnt++;
                    }else{
                        cnt = 0; 
                    }
                }
                cnt = 0; 
                for(int k = rows-1; k>=0; k--){
                    if(grid[k][i]=='0'){
                        dp[k][i] += cnt; 
                        max = Math.max(max, dp[k][i]); 
                    }else if(grid[k][i]=='E'){
                        cnt++;
                    }else{
                        cnt = 0;
                    }
                }
            }
            return max; 
        }
    }
    

  • 1
    Y

    @qian23 It is DP, running time O(m*n). It took me some time to figure out the logic.


  • 0
    C

    @Yun.Hu
    Hi can you tell me the time complexity of this solution?
    I cannot figure out why the time complexity is O(mn)?
    what is the worst time complexity?
    thank you!


  • 1
    S

    It's DP solution with complexity O (m*n).
    We traversing along the row, the enemies killed between any w's is same, since we are shifting to next column, we need to compute for each column. Even for columns the enemies killed between w's is same.


  • 0
    Y

    @Yun.Hu said in Simple DP solution in Java:

           if(grid[i][j] == '0'){
                max = (row + col[j] > max) ? row + col[j] : max;
            }
    

    This is a great answer! But I'm a little confused why the max value is only calculated when

    grid[i][j] =='0'
    does this imply you can only drop the bomb in an empty cell? Seems the question does not say that.


Log in to reply
 

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