题解 | #矩形覆盖#
矩形覆盖
http://www.nowcoder.com/practice/72a5a919508a4251859fb2cfb987a0e6
- 核心思想
每个大矩形都由上一个大矩形添加一个小矩形而得到，在添加小矩形的过程中有两种方法。
- 竖向添加：小矩形直接追加在大矩形的尾部
- 横向添加：小矩形要扭转一个已有的小矩形，组成一个正方形追加在大矩形尾部
当前矩形形态数f(n) = 竖向添加矩形+横向添加矩形
如果上一个大矩形是由横向两个小矩形结尾，则该大矩形不能被添加横向小矩形。如果上一个大矩形是由竖向的小矩形结尾，则该大矩形可以被添加横着矩形。
- 规律
- 在第n-1个大矩形基础上添加一个小矩形，得到第n个矩形。
- 第n-1个大矩形的所有形态都可以被添加竖向小矩形，这构成第n个矩形的竖向添加矩形，一共f(n-1)个。
- 第n-1个大矩形的部分形态可以被添加横向小矩形，其中由n-2横向扭转过来的形态不能被添加横向小矩形，由n-2竖向添加的形态可以被添加横向小矩形f(n-2),这构成第n个矩形的横向添加矩形，一共f(n-2)个。
- 第n个矩形的形态总数=竖向添加矩形f(n-1)+横向添加矩形f(n-2)
查看3道真题和解析