本文共 1173 字，大约阅读时间需要 3 分钟。

剑指offer打卡Day15: 矩形覆盖

题目描述

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

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

示例

输入

4

返回值

5

解析：

• 依照题目进行推导，并由此总结规律

  • 推导过程如图：
    

  • 由图中的结论不难看出这是一个斐波那契数列了，但具体是如何实现？

    • 以从n=3和n=4推导n=5的排列

    

    • 以从n=3和n=4推导n=5的排列

      

  • 不难得出结论：

    • 第n次组合数包含 由n-1加上一个竖着的矩形

    • 第n次组合数包含 由n-2加上两个横着的矩形

    • 递归公式为：

             |—— f[1] = 1 f[n] = |—— f[2] = 2       |—— f[n-1] + f[n-2]  (n>2)

  • 因此代码可以由递归，动态规划等思路完成

    • 参考

解答：

//递归：public int rectCover_withRecursion(int target) {       if (target < 1) {           return 0;    } else if (target == 1 || target == 2) {           return target;    } else {           return rectCover(target-1) + rectCover(target-2);    }}//动态规划：public int rectCover_withDp(int target) {       if(target == 1 || target == 0 || target == 2){           return target;    }    int[] dp = new int[target+1];    dp[0] = 0;    dp[1] = 1;    dp[2] = 2;    for(int i = 3; i <= target; i++){           dp[i] = dp[i-1] + dp[i-2];    }    return dp[target];}//动态规划继续优化public int rectCover——withDpImprove(int target) {       if(target==1 || target==2) return target;    int a = 1, b=2;    int c = 0;    for(int i=3;i<=target;i++){           c = b+a;        a = b;        b = c;    }    return c;}