使用Python计算3 x n方格内用2 x 1骨牌填充的方法数量
假设有一个数字n,我们需要找到用1 x 2骨牌填充(3 x n)方格的方法数量。如果需要,我们可以旋转这些骨牌。如果答案非常大,则返回该答案模10^9 + 7的值。
因此,如果输入为n = 4,则输出为11。
要解决此问题,我们将遵循以下步骤:
- m = 10^9 + 7
- 如果n是奇数,则返回0
- cs := 1, os := 0
- 对于i从2到n(递增2),做以下操作:
- cs := 3 * cs + os
- os := 2 * cs + os
- 返回(cs mod m)
更多Python相关文章,请阅读:Python 教程
示例(Python)
请看下面的实现以更好地理解:
class Solution:
def solve(self, n):
m = (10 ** 9 + 7)
if n % 2 == 1:
return 0
cs = 1
os = 0
for i in range(2, n + 1, 2):
cs, os = (3 * cs + os, 2 * cs + os,)
return cs % m
ob = Solution()
n = 4
print(ob.solve(n))
输入
4
输出
11