LC64 - 最小路径和

package DP2

import "math"

func minPathSum(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    dp := make([][]int, m)
    for i := 0; i < m; i++ {
        dp[i] = make([]int, n)
    }
    for i := m - 1; i >= 0; i-- {
        for j := n - 1; j >= 0; j-- {
            if i == m-1 && j == n-1 {
                dp[i][j] = grid[i][j]
            } else {
                p1, p2 := math.MaxInt, math.MaxInt
                if i != m-1 {
                    p1 = grid[i][j] + dp[i+1][j]
                }
                if j != n-1 {
                    p2 = grid[i][j] + dp[i][j+1]
                }
                dp[i][j] = min(p1, p2)
            }
        }
    }
    return dp[0][0]
}