64.Minimum Path Sum:修订间差异

来自WHY42
Riguz留言 | 贡献
Riguz留言 | 贡献
第28行: 第28行:


=Solution=
=Solution=
==DP+DFS==
==2D DP+DFS==
{{Submission|runtime=1ms|memory=43.47MB|rp=96.79|mp=95.08}}
<syntaxhighlight lang="java">
class Solution {
    /*
        1 2 3
        4 5 6
        注意二维数组的计算很容易搞错
    */
    private static final int NOT_REACHABLE = 1000000;
    private int cols;
    private int rows;
    private int[][]grid;
    private int[][]dp;
    public int minPathSum(int[][] grid) {
        this.grid = grid;
        this.cols = grid[0].length;
        this.rows = grid.length;
        this.dp = new int[rows][cols];
        for(int[] temp: dp)
            Arrays.fill(temp, NOT_REACHABLE);
       
        return findMinPath(0, 0);
    }
 
    private int findMinPath(int x, int y) {   
        if(x < cols && y < rows && dp[y][x] != NOT_REACHABLE){
            return dp[y][x];
        }
 
        if(x == cols -1 && y == rows -1) {
            return grid[y][x];
        }
       
        int current = grid[y][x];
        int min;
        if(x == cols -1) {
            // can only go down
            min = findMinPath(x, y+1);
        } else if(y == rows -1) {
            // can only go right
            min = findMinPath(x +1, y);
        } else {
            int down  = findMinPath(x, y+1);
            int right = findMinPath(x +1, y);
            min = Math.min(right, down);
        }
        return dp[y][x] = current + min;
    }
}
</syntaxhighlight>


[[Category:Algorithm]]
[[Category:Algorithm]]
[[Category:Dynamic Programming]]
[[Category:Dynamic Programming]]
[[Category:LeetCode]]
[[Category:LeetCode]]

2023年9月23日 (六) 10:45的版本

Description

#64 Minimum Path Sum Medium
Dynamic Programming Top 150
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example 1:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7

Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.


Example 2:

Input: grid = [[1,2,3],[4,5,6]]
Output: 12

Solution

2D DP+DFS

Runtime 1ms
Memory 43.47MB
class Solution {
    /* 
        1 2 3
        4 5 6
        注意二维数组的计算很容易搞错
    */
    private static final int NOT_REACHABLE = 1000000;
    private int cols;
    private int rows;
    private int[][]grid;
    private int[][]dp;
    public int minPathSum(int[][] grid) {
        this.grid = grid;
        this.cols = grid[0].length;
        this.rows = grid.length;
        this.dp = new int[rows][cols];
        for(int[] temp: dp)
            Arrays.fill(temp, NOT_REACHABLE);
        
        return findMinPath(0, 0);
    }

    private int findMinPath(int x, int y) {    
        if(x < cols && y < rows && dp[y][x] != NOT_REACHABLE){
            return dp[y][x];
        }

        if(x == cols -1 && y == rows -1) {
            return grid[y][x];
        }
        
        int current = grid[y][x];
        int min;
        if(x == cols -1) {
            // can only go down
            min = findMinPath(x, y+1);
        } else if(y == rows -1) {
            // can only go right
            min = findMinPath(x +1, y);
        } else {
            int down  = findMinPath(x, y+1);
            int right = findMinPath(x +1, y);
            min = Math.min(right, down);
        }
        return dp[y][x] = current + min;
    }
}