09（2）. 矩形覆盖 --剑指Offer(java版)

╰+哭是因爲堅強的太久メ 2022-03-10 09:09 179阅读 0赞

[github地址][github]

> 我们可以用2\*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2\*1的小矩形无重叠地覆盖一个2\*n的大矩形，总共有多少种方法？

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70][]

我自己分析的，下面是大佬总结的规律

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70 1][]

import java.util.*;
    public class Solution {
       Map<Integer, Integer> memo = new HashMap<>();
    
        public int RectCover(int target) {
            // 如果使用递归，如果其中有重复计算，那么最好使用数组或者其他容器存储中间结果，避免大量的重复计算.
            if (memo.get(target) == null) {
                if (target <= 0) {
                    return 0;
                }
                if (target * 2 == 2) {
                    memo.put(1,1);
                } else if (target * 2 == 4) {
                    memo.put(2,2);
                } else {
                    memo.put(target, RectCover((target - 1)) + RectCover(target - 2));
                }
            }
            return memo.get(target);
        }
    }

[github]: https://github.com/RudBob/offer66
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70]: /images/20220310/7e35a8f46b274e47ba235ecdfb161497.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70 1]: /images/20220310/d1375708672849afba912619e12b89ac.png

发表评论取消回复

表情：

评论列表（有 0 条评论，179人围观）

还没有评论，来说两句吧...

相关阅读

相关剑指offer 矩形覆盖

[剑指offer题型分类及各题的解题思路与代码（<---点我跳转 ^ - ^）][offer_---_ _ -] 1、题目描述我们可以用2\*1的小矩...

╰+哭是因爲堅強的太久メ/ 2024年04月18日 09:57/ 0 赞/ 81 阅读

相关剑指offer - 矩形覆盖

public class Solution { public int RectCover(int target) { int [

谁借莪１个温暖的怀抱￠/ 2022年09月25日 01:27/ 0 赞/ 180 阅读

相关剑指Offer | 矩形覆盖

做了个剑指Offer的题目目录，链接如下： [https://blog.csdn.net/mengmengdastyle/article/details/80317246]

左手的ㄟ右手/ 2022年05月25日 14:07/ 0 赞/ 191 阅读

相关剑指Offer | 矩形覆盖

做了个剑指Offer的题目目录，链接如下： [https://blog.csdn.net/mengmengdastyle/article/details/80317246]

曾经终败给现在/ 2022年05月24日 00:23/ 0 赞/ 215 阅读

相关剑指offer：矩形覆盖

题目描述我们可以用2\1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2\1的小矩形无重叠地覆盖一个2\n的大矩形，总共有多少种方法？链接：[https://ww

绝地灬酷狼/ 2022年04月14日 05:13/ 0 赞/ 248 阅读

相关剑指offer矩形覆盖

原题目链接：[剑指offer矩形覆盖][offer] -------------------- 分类剑指offer 递归 ------------------

忘是亡心i/ 2022年04月13日 15:20/ 0 赞/ 261 阅读

相关剑指Offer-矩形覆盖

题目描述我们可以用2×1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2×1的小矩形无重叠地覆盖一个2×n的大矩形，总共有多少种方法？解题思路：n=1时，有1种方

骑猪看日落/ 2022年03月01日 08:38/ 0 赞/ 265 阅读

相关剑指offer-矩形覆盖

题目描述我们可以用2\ 1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2\ 1的小矩形无重叠地覆盖一个2\ n的大矩形，总共有多少种方法？实现思想依旧是

﹏ヽ暗。殇╰゛Y/ 2022年02月16日 10:58/ 0 赞/ 282 阅读

相关剑指Offer（十）矩形覆盖（Java版 )

一、题目描述我们可以用2\1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2\1的小矩形无重叠地覆盖一个2\n的大矩形，总共有多少种方法？二、题目分析第一

今天药忘吃喽~/ 2021年09月26日 22:28/ 0 赞/ 259 阅读

相关剑指offer：矩形覆盖

试题：我们可以用2\1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2\1的小矩形无重叠地覆盖一个2\n的大矩形，总共有多少种方法？代码：同样是总结出规律，然后使

冷不防/ 2021年06月24日 16:00/ 0 赞/ 501 阅读