leetcode每日一題練習 使用golang和java實作 動态規劃 最小路徑和

題目要求

給定一個包含非負整數的 m x n 網格，請找出一條從左上角到右下角的路徑，使得路徑上的數字總和為最小。傳回路徑最小值。

解題思路：動态規劃

這道題明顯就是動态規劃，因為它滿足将一個大問題分成許多小問題，而且每一個小問題的結果會對最終結果産生影響。這道題屬于一個正向的dp問題。

首先處理(0,0)的資料，将其原封不動的放入dp數組，而且該位置相鄰的兩條邊隻有一個通路，是以直接與前一個資料相加，作為到達該點的最小路徑。其他資料每個資料比較兩個通路，哪一個更好一點，進而得到最優解。

用golang實作

func minPathSum(grid [][]int) int {
    if len(grid) == 0 || len(grid[0]) == 0 {
        return 0
    }
    m, n := len(grid), len(grid[0])
    dp := make([][]int, m)
    for i := 0; i < len(dp); i++ {
        dp[i] = make([]int, n)
    }
    dp[0][0] = grid[0][0]
    for i := 1; i < m; i++ {
        dp[i][0] = dp[i - 1][0] + grid[i][0]
    }
    for j := 1; j < n; j++ {
        dp[0][j] = dp[0][j - 1] + grid[0][j]
    }
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
        }
    }
    return dp[m - 1][n - 1]
}

func min(a int,b int)int {
    if a>b{
        return b
    }else{
        return a
    }
}
           

時間複雜度：O（mn）我們使用了一個m x n的循環。

空間複雜度：O（mn）因為我們使用了一個dp[m][n]的數組。

使用java實作

class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }
}