力扣学院打卡最后一天

今天是最后一天啦！但仅仅是打卡的最后一天，刷题还是会继续下去的！！！

今天的一道中等题：

dp题一直是我的噩梦~

算法思想：

考虑这么一种平铺的方式：在第 i 列前面的正方形都被瓷砖覆盖，在第 i 列后面的正方形都没有被瓷砖覆盖（i从 1开始计数）。那么第 i 列的正方形有四种被覆盖的情况：

一个正方形都没有被覆盖，记为状态 0；

只有上方的正方形被覆盖，记为状态 1；

只有下方的正方形被覆盖，记为状态 2；

上下两个正方形都被覆盖，记为状态 3。

使用 dp[i][s] 表示平铺到第 i 列时，各个状态 s对应的平铺方法数量。考虑第 i−1 列和第 i列正方形

 代码：

class Solution:
    def numTilings(self, n: int) -> int:
        MOD = 10**9+ 7
        '''1e9  是带小数点的！！！
10**9是不带小数点的！！！！，如果用1e9取模，记得最后要转换为int！！！！'''
        dp = [[0] * 4 for _ in range(n + 1)]
        dp[0][3] = 1
        for i in range(1, n + 1):
            dp[i][0] = dp[i - 1][3]
            dp[i][1] = dp[i - 1][0] + dp[i - 1][2]
            dp[i][2] = dp[i - 1][0] + dp[i - 1][1]
            dp[i][3] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3]
            for j in range(1,4):
                if dp[i][j]>=MOD:
                    dp[i][j]-=MOD
        
        return dp[n][3]%MOD 

运行结果：

 最后一天的打卡完成！！！但是每日一题会继续~~~~~