首页 > 试题广场 > 矩形覆盖
[编程题]矩形覆盖
  • 热度指数:407679 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?
头像 Jalr4ever
发表于 2019-08-08 02:06:50
迭代 涂掉最后一级矩形的时候,是用什么方式完成的? n = 1 的时候 只能横着覆盖,一种 n = 2 的时候 可以横着和竖着覆盖,两种 n = 3 的时候 第三级横着覆盖,用了一级,剩下 n = 2,有两种覆盖方法 第三季竖着覆盖,用了两级,剩下 n = 1,有一种覆盖方法 总共有 展开全文
头像 Janebook2019
发表于 2019-08-12 22:44:37
Java递归实现 public class Solution { public int RectCover(int target) { // 被覆盖的目标矩形的形状: 2*n // 每次新增加的一列,(1)如果竖着放对应的情况与 target为 n-1 时相同 展开全文
头像 小薛ssp
发表于 2020-01-02 21:01:35
解释:菲波那切数列本质 class Solution: def rectCover(self, number): # write code here if number == 0: return 0 if number 展开全文
头像 把牛妹带回家
发表于 2019-07-26 15:46:39
依旧和上题一样递归,模板一样同样的味道,同样的感觉 # -*- coding:utf-8 -*- class Solution: def rectCover(self, number): # write code here if number==0: 展开全文
头像 少一块星空
发表于 2019-12-28 09:35:01
这个问题同样是一个斐波那契数列问题,首先判断当number输入小于0的情况,这时候应该返回None; 否则则是小于等于1的情况,即0,1的两种情况,这时候返回的应该同样是0,1,所以return number; 最后就是大于1的情况,当等于2时,考虑最后一步如果是横着,则剩下的是f(1)中情况,如果 展开全文
头像 许愿_offer++
发表于 2019-07-31 00:27:39
特殊的target=0时输出0,其他时候还是斐波那契递归。 一个2*n的矩形,可以分为两种方式填充 1、2*(n-1)  + 2*1 ,此时只要把RectCover(n-1)的那种,再拼接一个竖的2*1的就可以了,方法数目为RectCover(n-1) 2、2*(n-1) + 2* 展开全文
头像 郭家兴0624
发表于 2019-08-10 10:17:55
题目描述 我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法? 思路:依旧是斐波那契数列,讨论区中有很多作图解释方便理解。注意n<1的情况。 AC代码: def rectCover(self, number): # 展开全文
头像 Acoer
发表于 2020-01-13 16:48:53
套路:如果遇到找存在多少种方法的时候,多半是求解一个方程,即采用递归方法;可以先从低层矩阵找到规律:2×1层台阶:1种2×2层台阶:2种2×3层台阶:3种2×4层台阶:5种不难推测出 f(n) = f(n-1) + f(n-2)代码如下: public class Solution { pu 展开全文
头像 TLE
发表于 2019-08-29 16:12:50
经典题,思想很好,小白可以多读几遍分析思路!(P79) class Mat { // 矩阵对象 int n = 2; int m[][] = new int[n][n]; public Mat mul(Mat a) { // 矩阵乘法 Mat b = new 展开全文