こんにちは
今回の学びは
・結果、入力に0がる場合にはif up: などNone判定は明示的に`if up is not None`としよう
問題はhttps://leetcode.com/problems/minimum-path-sum/
（時間配分は5分問題理解 10分検討 10分実装 20分振り返り の一文45分構成)
終始、わからないことは声にだして、明確にしていきましょう。
１，まずは入出力をしっかりおさえましょう。（問題を自分の言葉で復唱すること、わからないことをクリアにすると）
２，いくつかのソリューションを声にだして出してみましょう。（もちろんtime complexit, space complexityの分析を付け加えて）
３，どれでいくか、一緒に決定しましょう。
timespace analysis (時間とスペースの分析）は 〇〇です
O(N^2)
場合によっては、pseudocode（擬似コード）をかいてみてもよい。
４、実装しましょう。
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
if grid is None or len(grid) == 0 or len(grid[0])==0: return None
m = len(grid[0])
n = len(grid)
dp = [[0] * m for _ in range(n)]
for i in range(n):
for j in range(m):
up = dp[i-1][j] if i >= 1 else None
left = dp[i][j-1] if j >= 1 else None
curr = grid[i][j]
if up is not None and left is not None: path = min(up, left)
elif up is not None: path = up
elif left is not None: path = left
else:
path = 0
dp[i][j] = path + curr
return dp[i][j]
５、エッジケースとサンプルテストを忘れずに！
通らないコード
https://leetcode.com/submissions/detail/292204437/
inputが以下のとき、63であるべきが、64となっていた。このように60/61 failedのようにテストケースの最後の方は
入力も大きく、これまでのテストケースはクリアしている分、かなりデバッグしにくいです。
今回、私は怪しい箇所、path = 0のところにブレークをいれてIDEでデバッグしました。手ではかなり骨が折れる作業ですので、
手でやれと言われたら、20分かかりますけどいいですか？とか断りたいところ。
[[0,2,2,6,4,1,6,2,9,9,5,8,4,4],[0,3,6,4,5,5,9,7,8,3,9,9,5,4],[6,9,0,7,2,2,5,6,3,1,0,4,2,5],[3,8,2,3,2,8,8,7,5,9,6,3,4,5],[4,0,1,3,9,2,0,1,6,7,9,2,8,9],[6,2,7,9,0,9,5,2,7,5,1,4,4,7],[9,8,3,3,0,6,8,0,8,8,3,5,7,3],[7,7,4,5,9,1,5,0,2,2,2,1,7,4],[5,1,3,4,1,6,0,4,3,8,4,3,9,9],[0,6,4,9,4,1,5,5,4,2,5,7,4,0],[0,1,6,6,4,9,2,7,8,2,1,3,3,7],[8,4,9,9,2,3,8,6,6,5,4,1,7,9]]
結果、入力に0がる場合にはif up: などNone判定は明示的に`if up is not None`としよう
というものでした。つまり最初のバグ入りの箇所は
if up and left: path = min(up, left) elif up: path = up elif left: path = left else: path = 0
こすべきであった。
if up is not None and left is not None: path = min(up, left) elif up is not None: path = up elif left is not None: path = left else: path = 0
振り返り
「次のこの問題を解くばあい知っていればよい一つの事実とは？」
まとめ
・結果、入力に0がる場合にはif up: などNone判定は明示的に`if up is not None`としよう
以上です