0064.最小路径和

https://leetcode.cn/problems/minimum-path-sum/

方法一：动态规划

时间复杂度 $O(m \times n)$，空间复杂度 $O(n)$，其中 m 和 n 分别表示 grid 数组的行数和列数。

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

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