首页 > 试题广场 > 矩形覆盖
[编程题]矩形覆盖
  • 热度指数:497508 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?

比如n=3时,2*3的矩形块有3种覆盖方法:

头像 牛客官方题解
发表于 2020-05-29 14:59:57
精华题解 描述: 这是一道规律题。 知识点:递归,记忆递归,动态规划,递推 难度::一星 题解: 方法一:递推 对于这种题没有思路怎么办? 那就对n 从小到大,一步步分析: n=1时,显然只有一种方法 n=2时,如图有2种方法 展开全文
头像 Jalr4ever
发表于 2019-08-08 02:06:50
迭代 涂掉最后一级矩形的时候,是用什么方式完成的? n = 1 的时候 只能横着覆盖,一种 n = 2 的时候 可以横着和竖着覆盖,两种 n = 3 的时候 第三级横着覆盖,用了一级,剩下 n = 2,有两种覆盖方法 第三季竖着覆盖,用了两级,剩下 n = 1,有一种覆盖方法 总共有 展开全文
头像 struggle201907102230352
发表于 2020-02-10 16:38:17
简单的递归 当n=1时,只能竖着覆盖,f(1)=1; 当n=2时,既可以横着覆盖,也可以竖着覆盖,f(2)=2; 当n=N时,只需要考虑第一块如何覆盖即可,详见下图: 代码如下: public int rectCover(int target) { if (target 展开全文
头像 Janebook2019
发表于 2019-08-12 22:44:37
Java递归实现 public class Solution { public int RectCover(int target) { // 被覆盖的目标矩形的形状: 2*n // 每次新增加的一列,(1)如果竖着放对应的情况与 target为 n-1 时相同 展开全文
头像 年少挽剑世无双·
发表于 2020-03-05 19:05:11
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法? 比如n=3时,2*3的矩形块有3种覆盖方法: 解答:思想:和跳台阶类似,小矩形竖着放相当于跳一级台阶,横着放相当于跳两级台阶,所以可以复用跳台阶的代码(见第八题)。 pub 展开全文
头像 南宫雨雪
发表于 2020-01-26 12:57:56
问题分析:对于很多递归问题,我们都可以通过归纳总结来找出他们的规律:当n=1时,way=1(横或竖)当n=2时,way=2(全横或全竖)当n=3时,way=3(全竖&横横竖&竖横横)当n=4时,way=5(全竖&全横&竖横横竖&竖竖横横&横横竖竖)当n 展开全文
头像 铁柱锈死了
发表于 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)中情况,如果 展开全文
头像 念今心
发表于 2020-03-12 17:14:48
int rectCover(int matrix) { if(matrix==0) return 0; if(matrix==1) return 1; if(matrix==2) return 2; return re 展开全文
头像 JokerC
发表于 2020-05-23 14:58:05
和青蛙跳台阶类似,其实就是个Fibonacci 数列