いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode medium 64 minimum path sum

投稿日:

こんにちは

今回の学びは

・結果、入力に0がる場合にはif up: などNone判定は明示的に`if up is not None`としよう

 

問題はhttps://leetcode.com/problems/minimum-path-sum/

(時間配分は5分問題理解 10分検討 10分実装  20分振り返り の一文45分構成)

終始、わからないことは声にだして、明確にしていきましょう。

1,まずは入出力をしっかりおさえましょう。(問題を自分の言葉で復唱すること、わからないことをクリアにすると)

 

2,いくつかのソリューションを声にだして出してみましょう。(もちろんtime complexit, space complexityの分析を付け加えて)

 

3,どれでいくか、一緒に決定しましょう。

timespace analysis (時間とスペースの分析)は 〇〇です

O(N^2)

場合によっては、pseudocode(擬似コード)をかいてみてもよい。

 

4、実装しましょう。

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]

5、エッジケースとサンプルテストを忘れずに!

通らないコード

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`としよう

以上です

-アルゴリズム

Copyright© CTOの日記 , 2020 All Rights Reserved.