10 图解剑指Offer 矩形覆盖 Java题解

野性酷女 2023-02-20 08:23 37阅读 0赞

### 10 图解剑指Offer 矩形覆盖 Java题解 ###

*  10 图解剑指Offer 矩形覆盖 Java题解
 *   *   *  题目链接
         *  题目描述
         *  题解:
         *  图解:
         *  代码:
         *  复杂度

# 10 图解剑指Offer 矩形覆盖 Java题解 #

### [题目链接][Link 1] ###

### 题目描述 ###

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

比如n=3时，2\*3的矩形块有3种覆盖方法：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3_size_16_color_FFFFFF_t_70]

### 题解: ###

具体看图解

思路: 斐波那契额数列问题，此题前n项和公式 f(n) = f(n - 1) + f(n -2) **(n>2)**  
注意此题 target = 0 结果为0， target = 1 结果为 1 ，target = 2 结果为2 与普通斐波那契额数列不同，n从3开始。  
根据公式可以用递归解决此类问题，但是太耗费时间不推荐，递归的思想是重复的解决子问题。  
故采用记忆优化的算法，将递归子问题的结果存入hashMap中，就可以避免重复计算子问题的结果。计算f(n) 需要计算f(n -1) f(n- 2) ,f(n -1) 和 f(n -2)的计算也要以此类推。  
又因为f(n) = f(n -1) + f(n - 2) 故最后只需要三个变量a，b，sum，遍历数列，在依次将和改为下一个和，即可实现。sum = a +b a = b b = sum。 最后 返回 a即可

### 图解: ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3_size_16_color_FFFFFF_t_70 1]

### 代码: ###

public class Solution { 
        public int RectCover(int target) { 
           if(target == 0 || target == 1 || target == 2) return target;
           int a = 1, b = 2,sum;
            
           for(int i = 2;i < target; i++){ 
               sum = a + b;
               a = b;
               b = sum;
           }
           return b;
        }
    }

### 复杂度 ###

空间复杂度: 空间复杂度为O(1) 三个int型空间。  
最坏时间复杂度: 遍历时间复杂度O(n)

[Link 1]: https://www.nowcoder.com/practice/72a5a919508a4251859fb2cfb987a0e6?tpId=13&&tqId=11163&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200625192937864.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200625193255758.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3,size_16,color_FFFFFF,t_70