【アルゴリズム脳トレ】leetcode medium 790 Domino and Tromino Tiling

こんにちは

今回の学びは

・ソートされた配列と二分木はよく似てるよ。

・できれば二分木探索を配列で実装していて 🙂

問題はdomino-and-tromino-tiling

（時間配分は5分問題理解=restate&clarify　10分検討multip-sol, analysis, reasons 10分実装  20分振り返り　の一文45分構成)をできればgoogle docで笑&真剣。

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

１，まずは入出力をしっかりおさえましょう。（問題を自分の言葉で復唱すること、わからないことをクリアにすると、前提も声にだすこと）

２，いくつかのソリューションを声にだして出してみましょう。（もちろんtime complexit, space complexityの分析や理由を付け加えて）

３，どれでいくか、一緒に決定しましょう。（理由付きでね、よろしく）

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

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

動画はこちら。

４、実装しましょう。

https://leetcode.com/problems/domino-and-tromino-tiling/discuss/406649/Python-DP-half-and-full
分かりやすい

https://leetcode.com/problems/domino-and-tromino-tiling/discuss/182594/Python-1-liner-O(log-n)-time-O(1)-space-with-explanation
わかりやすいけど、
すごいけど、わからない。

class Solution:
    def numTilings(self, n: int) -> int:
        if n == 0: return 0
        dp = [0] * (n+1)
        dp[0] = 0
        if n == 0: return dp[0]
        dp[1] = 1
        if n == 1: return dp[1]
        dp[2] = 2
        if n == 2: return dp[2]
        dp[3] = 5
        if n == 3: return dp[3]
        for i in range(4, n+1):
            dp[i] = dp[i-1]*2 + dp[i-2]*0  + dp[i-3]*1
            #dp[i] = dp[i-1]*0 + dp[i-2]*2  + dp[i-3]*1
            #dp[i] = dp[i-1] + dp[i-2]*2  + dp[i-3]*2
            # https://leetcode.com/problems/domino-and-tromino-tiling/discuss/407367/Python-O(0)-space
            #dp[i] = dp[i-1] + dp[i-2]*2  + dp[i-3]*5
            #dp[i] = dp[i-1] + dp[i-2]*2  + dp[i-3]*2

        return dp[n]

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

振り返り

「次のこの問題を解くばあい知っていればよい一つの事実とは？」

まとめ

以上です