0064_minimum-path-sum

README

0064_minimum-path-sum

最基础的dp!!!

题目要求只能向右或者向下走.

设 dp[i][j] 是从左上到达该点的答案, 则:

• 第一列和第一行只有一种走法
• 除第一列和第一行, dp[i][j] = min{ dp[i-1][j], dp[i][j-1] } + grid[i][j]

如果对空间要求严格, 且可以改变输入, 我们可以把dp数据直接覆盖到输入上.

更多

考虑允许向左或者向上走的情况:

• 如果可以向左或者向上走, 格子都为正数的情况绝对不会是最优解
  • 如果格子可为0...?
  • 如果格子值可为负
    • 不限制步数的话, 可能会出现循环踩两个格子的情况
    • 每个格子只能走一遍...?