【leetcode】64. 最小路径和

题目

64. 最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

题解

动态规划

1. 二维数组dp
2. 定义边界的dp
3. 定义状态转移方程 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

class Solution(object):def minPathSum(self, grid):""":type grid: List[List[int]]:rtype: int"""m = len(grid)n = len(grid[0])dp = [[0] * n for _ in range(m)]dp[0][0] = grid[0][0]for i in range(1, n):dp[0][i] = dp[0][i - 1] + grid[0][i]for j in range(1, m):dp[j][0] = dp[j - 1][0] + grid[j][0]for i in range(1, m):for j in range(1, n):dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]print(dp)print(dp[m - 1][n - 1])return dp[-1][-1]