用js刷剑指offer(矩形覆盖)
2024-09-01 14:11:57
题目描述
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?
思路
依旧是斐波那契数列
2 * n的大矩形,和n个2 * 1的小矩形
其中target * 2为大矩阵的大小
有以下几种情形:
1⃣️target <= 0 大矩形为<= 2 * 0,直接return 1;
2⃣️target = 1大矩形为2 * 1,只有一种摆放方法,return1;
3⃣️target = 2 大矩形为2 * 2,有两种摆放方法,return2;
4⃣️target = n 分为两步考虑:
第一次摆放一块 2 * 1 的小矩阵,则摆放方法总共为f(target - 1)
第一次摆放一块1 * 2的小矩阵,则摆放方法总共为f(target-2)
因为,摆放了一块1 * 2的小矩阵(用√√表示),对应下方的1 * 2(用××表示)摆放方法就确定了,所以为f(targte-2)
js代码
function rectCover(number)
{
// write code here
if (number <= 0) return 0
if (number === 1) return 1
if (number === 2) return 2
let prePre = 1
let pre = 2
let now
for (let i = 3; i <= number; i++){
now = prePre + pre
prePre = pre
pre = now
}
return now
}
最新文章
- HCP查询配置
- 《InsideUE4》-7-GamePlay架构(六)PlayerController和AIController
- php HTTP Auth
- HDFS读写数据块--${dfs.data.dir}选择策略
- 学习RxJS: 导入
- MyEclipse项目中的java文件的图标变成空心的问题
- iOS ARC下循环引用的问题 -举例说明strong和weak的区别
- db.class的实现类
- web攻击方式和防御方法
- Ubuntu操作系统下安装JDK、tomcat、mysql
- 201521123089 《Java程序设计》第3周学习总结
- Linux 系统裁剪笔记 软盘2
- MySql在生产环境中是用mysqldump还是xtrabackup备份和恢复数据
- 【XSY3154】入门多项式 高斯消元
- 叩响C#之门-继承
- Judy Beta 阶段整体计划
- jQuery基础2
- O(big oh) (big omega) (big theta)
- xml解析 使用dom4j操作xml
- 学习 已经登录windows的情况下获取windows的密码