43 lines
1.9 KiB
Java
43 lines
1.9 KiB
Java
# 10.2 矩形覆盖
|
||
|
||
## 题目链接
|
||
|
||
[牛客网](https://www.nowcoder.com/practice/72a5a919508a4251859fb2cfb987a0e6?tpId=13&tqId=11163&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking&from=cyc_github)
|
||
|
||
## 题目描述
|
||
|
||
我们可以用 2\*1 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2\*1 的小矩形无重叠地覆盖一个 2\*n 的大矩形，总共有多少种方法？
|
||
|
||
<div align="center"> <img src="https://cs-notes-1256109796.cos.ap-guangzhou.myqcloud.com/b903fda8-07d0-46a7-91a7-e803892895cf.gif" width="100px"> </div><br>
|
||
|
||
## 解题思路
|
||
|
||
当 n 为 1 时，只有一种覆盖方法：
|
||
|
||
<div align="center"> <img src="https://cs-notes-1256109796.cos.ap-guangzhou.myqcloud.com/f6e146f1-57ad-411b-beb3-770a142164ef.png" width="100px"> </div><br>
|
||
|
||
当 n 为 2 时，有两种覆盖方法：
|
||
|
||
<div align="center"> <img src="https://cs-notes-1256109796.cos.ap-guangzhou.myqcloud.com/fb3b8f7a-4293-4a38-aae1-62284db979a3.png" width="200px"> </div><br>
|
||
|
||
要覆盖 2\*n 的大矩形，可以先覆盖 2\*1 的矩形，再覆盖 2\*(n-1) 的矩形；或者先覆盖 2\*2 的矩形，再覆盖 2\*(n-2) 的矩形。而覆盖 2\*(n-1) 和 2\*(n-2) 的矩形可以看成子问题。该问题的递推公式如下：
|
||
|
||
<!-- <div align="center"><img src="https://latex.codecogs.com/gif.latex?f(n)=\left\{\begin{array}{rcl}1&&{n=1}\\2&&{n=2}\\f(n-1)+f(n-2)&&{n>1}\end{array}\right." class="mathjax-pic"/></div> <br> -->
|
||
|
||
<div align="center"> <img src="https://cs-notes-1256109796.cos.ap-guangzhou.myqcloud.com/508c6e52-9f93-44ed-b6b9-e69050e14807.jpg" width="370px"> </div><br>
|
||
|
||
```java
|
||
public int rectCover(int n) {
|
||
if (n <= 2)
|
||
return n;
|
||
int pre2 = 1, pre1 = 2;
|
||
int result = 0;
|
||
for (int i = 3; i <= n; i++) {
|
||
result = pre2 + pre1;
|
||
pre2 = pre1;
|
||
pre1 = result;
|
||
}
|
||
return result;
|
||
}
|
||
```
|