赞
踩
给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
示例 1:
输入:grid = [[1,3,1],[1,5,1],[4,2,1]]
输出:7
解释:因为路径 1→3→1→1→1 的总和最小。
示例 2:
输入:grid = [[1,2,3],[4,5,6]]
输出:12
from typing import List class Solution: def minPathSum(self, grid: List[List[int]]) -> int: if len(grid) == 0: return 0 row = len(grid) col = len(grid[0]) res = [[0] * col for _ in range(row)] for i in range(row): for j in range(col): if i - 1 < 0 and j - 1 < 0: res[i][j] = grid[i][j] elif i - 1 < 0: res[i][j] = res[i][j - 1] + grid[i][j] elif j - 1 < 0: res[i][j] = res[i - 1][j] + grid[i][j] else: res[i][j] = min(res[i][j - 1], res[i - 1][j]) + grid[i][j] return res[row - 1][col - 1] if __name__ == "__main__": s = Solution() grid = [[1,3,1],[1,5,1],[4,2,1]] a = s.minPathSum(grid) print(a)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。