Categorías
Algorithms Interview

LeetCode – Suma de ruta mínima (Java)

Dada la cuadrícula amxn llena de números no negativos, busque una ruta de arriba a la izquierda a la parte inferior derecha que minimice la suma de todos los números a lo largo de su ruta.

Solución 1 de Java: búsqueda en profundidad

Una solución nativa sería la búsqueda en profundidad. Es tiempo es demasiado caro y falla el juicio en línea.

public int minPathSum(int[][] grid) {
    return dfs(0,0,grid);
}
 
public int dfs(int i, int j, int[][] grid){
    if(i==grid.length-1 && j==grid[0].length-1){
        return grid[i][j];
    }
 
    if(i<grid.length-1 && j<grid[0].length-1){
        int r1 = grid[i][j] + dfs(i+1, j, grid);
        int r2 = grid[i][j] + dfs(i, j+1, grid);
        return Math.min(r1,r2);
    }
 
    if(i<grid.length-1){
        return grid[i][j] + dfs(i+1, j, grid);
    }
 
    if(j<grid[0].length-1){
        return grid[i][j] + dfs(i, j+1, grid);
    }
 
    return 0;
}

Solución Java 2: Programación dinámica

public int minPathSum(int[][] grid) {
    if(grid == null || grid.length==0)
        return 0;
 
    int m = grid.length;
    int n = grid[0].length;
 
    int[][] dp = new int[m][n];
    dp[0][0] = grid[0][0];    
 
    // initialize top row
    for(int i=1; i<n; i++){
        dp[0][i] = dp[0][i-1] + grid[0][i];
    }
 
    // initialize left column
    for(int j=1; j<m; j++){
        dp[j][0] = dp[j-1][0] + grid[j][0];
    }
 
    // fill up the dp table
    for(int i=1; i<m; i++){
        for(int j=1; j<n; j++){
            if(dp[i-1][j] > dp[i][j-1]){
                dp[i][j] = dp[i][j-1] + grid[i][j];
            }else{
                dp[i][j] = dp[i-1][j] + grid[i][j];
            }
        }
    }
 
    return dp[m-1][n-1];
}

Por Programación.Click

Más de 20 años programando en diferentes lenguajes de programación. Apasionado del code clean y el terminar lo que se empieza. ¿Programamos de verdad?

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *