有1×n的一个长方形,用一个1×1、1×2和1×3的骨牌铺满方格,求共有多少种浦铺法。例如当n=3时为1×3的方格。此时用1×1、1×2和1×3的骨牌铺满方格,共有四种铺法,如下图所示。求:1×n时,有多少种铺法?用程序写出来
时间: 2023-05-25 07:06:51 浏览: 372
这是一道动态规划的经典问题,可以用递推式来解决。假设f(n)表示1×n的方格铺满的方法数,根据骨牌的种类可以得到以下递推式:
f(n) = f(n-1) + f(n-2) + f(n-3)
其中f(n-1)表示最后一块是1×1的骨牌铺满的方法数,f(n-2)表示最后一块是1×2的骨牌铺满的方法数,f(n-3)表示最后一块是1×3的骨牌铺满的方法数。因为1×1、1×2和1×3的骨牌都是连着放的,所以每种骨牌铺完之后剩下的部分就可以转化为f(n-1)、f(n-2)和f(n-3)的子问题。
初始值f(0)=1,f(1)=1,f(2)=2。因为当n=0或1或2时,方格都已经被铺满了,所以铺法只有一种。
代码如下:
def tiling(n):
if n < 3:
return 1 if n == 0 else 2
f = [0] * (n + 1)
f[0], f[1], f[2] = 1, 1, 2
for i in range(3, n + 1):
f[i] = f[i-1] + f[i-2] + f[i-3]
return f[n]
print(tiling(3)) # 4
print(tiling(5)) # 13
print(tiling(8)) # 153
相关问题
有 2*n 的一个长方形方格,用一个 1 * 2 的骨牌铺满方格
题目描述:在2×n的一个长方形方格中,用一个1×2的骨牌铺满方格,输入n,输出铺放方案的总数。
解题思路:这是一道典型的动态规划问题。我们可以用f(n)表示铺满2×n方格的方案数。对于第一列,我们可以竖着放一块骨牌,这样就剩下2×(n-1)的方格需要铺满,方案数为f(n-1);或者横着放两块骨牌,这样就剩下2×(n-2)的方格需要铺满,方案数为f(n-2)。因此,f(n)=f(n-1)+f(n-2)。
代码实现:
题目描述:在2×n的一个长方形方格中,用一个1×2的骨牌铺满方格,输入n,输出铺放方案的总数。
这是一道经典的动态规划问题,可以使用动态规划来解决。
定义状态:设f[i]表示2×i的长方形方格中铺放方案的总数。
状态转移方程:对于第i列,可以竖着放一块1×2的骨牌,或者横着放两块1×1的骨牌。如果竖着放一块骨牌,那么第i-1列必须也竖着放一块骨牌,此时方案数为f[i-2];如果横着放两块骨牌,那么第i-1列必须也是横着放两块骨牌,此时方案数为f[i-2];如果第i列不放骨牌,那么方案数为f[i-1]。因此,状态转移方程为:f[i] = f[i-1] + f[i-2]。
边界条件:f[1]=1,f[2]=2。
最终答案为f[n]。
下面是Python代码实现:
```python
def tilingRectangle(n: int) -> int:
if n == 1:
return 1
if n == 2:
return 2
f = [1, 2]
for i in range(3, n + 1):
f.append(f[-1] + f[-2])
return f[-1]
```
时间复杂度为O(n),空间复杂度为O(n)。
相关推荐
![md](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)