64. Minimum Path Sum
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
Example:
Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.
动态规划的4点要素:
- 状态 State 灵感,创造力,存储小规模问题的结果,很重要!!!
- 方程 Function 状态之间的联系,怎么通过小的状态,来算大的状态
- 初始化 Intialization 最极限的小状态是什么, 起点
- 答案 Answer 最大的那个状态是什么,终点
状态网格 State Grid:
dy[x][y] = d[x-1][y] or d[x][y-1] + grid[x][y]
class Solution(object):
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
r = len(grid)
c = len(grid[0])
dy = grid
# dy[x][y] = d[x-1][y] or d[x][y-1] + grid[x][y]
for x in range(r):
for y in range(c):
if x == 0 and y==0:
continue
print('1')
elif x==0:
dy[x][y] = dy[x][y-1] + grid[x][y]
elif y==0:
dy[x][y] = dy[x-1][y] + grid[x][y]
else:
a = dy[x][y-1] + grid[x][y]
b = dy[x-1][y] + grid[x][y]
dy[x][y] = b if a > b else a
return dy[r-1][c-1]
请多多指教。
文章标题:64. Minimum Path Sum
本文作者:顺强
发布时间:2019-07-21, 23:59:00
原始链接:http://shunqiang.ml/leetcode-64-min-path-sun/版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。