当你的才华还撑不起你的野心时,你应该静下心去学习 。
题目描述
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形,从同一个方向看总共有多少种不同的方法?
比如n=3时,2*3的矩形块有3种不同的覆盖方法(从同一个方向看):
示例
假设f [n]表示2*n大矩阵的方法数。 如果你下用数学归纳法,先从简单的n=1、2、3开始计算,可以得出:f[n] = f[n-1] + f[n-2],初始条件f[1] = 1, f[2] =2 是不是感觉简单的斐波那契数列做了三天?
复杂度分析: 时间复杂度 O(N) : 计算 f(n) 需循环 n 次,每轮循环内计算操作使用 O(1) 。 空间复杂度 O(1) : 几个标志变量使用常数大小的额外空间。
参考代码 Java版本public class Solution {
public int RectCover(int target) {
// 被覆盖的目标矩形的形状: 2*n
// 每次新增加的一列,(1)如果竖着放对应的情况与 target为 n-1 时相同;
// (2如果横着放,对应的情况与 target 为 n-2 时相同。
if(target
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?