ZhangLei的博客

ZhangLei的博客

题目描述

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

解法1

一开始尝试解这道题的时候其实有些不知道怎么下手,花了很长时间。后来才发现可以利用递归的思想,将n的值不断放小到某个可以直接知道结果的值。虽然直接实现递归的算法可能效率不高,但在找到题目的递归解法后,再在递归算法的基础上做优化,就可以得到一个满意的答案。
回到本题,用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,假设有F(n)中方法
先用一个2*1的小矩形,竖着覆盖大矩形,如下图所示。则还剩下2*(n-1)的大矩形需要覆盖,即有F(n-1)种方法
【剑指Offer】矩形覆盖-LMLPHP

如果先用一个2*1的小矩形,横着覆盖大矩形,如下图所示。则底部的红色区域也只能用一个2*1的小矩形横着覆盖。则还剩下2*(n-2)的大矩形需要覆盖,即有F(n-2)中方法
【剑指Offer】矩形覆盖-LMLPHP

由以上两种情况可知,F(n) = F(n - 1) + F(n - 2),我们只需要知道F(0),F(1),就可以求得F(n)。很明显这是一个斐波那契数列的定义。对于斐波那契数列的多种求解方法可以参考【剑指Offer】斐波那契数列
当n = 0的时候,显然有0中覆盖方法,即F(0) = 0
当n = 1的时候,只有一种覆盖方法,即F(1) = 1
我们可以直接使用直观的递归算法求解,如下所示

实现代码

public int rectCover(int number)
{
    if (number <= 0)
        return 0;
    if (number == 1)
        return 1;
    else if (number == 2)
        return 2;
    return rectCover(number - 1) + rectCover(number - 2);
}

解法2

可以使用循环迭代的方式优化递归算法,如下所示

实现代码

public int rectCoverOptimize(int number)
{
    int f = 0, g = 1;
    while (number-- > 0)
    {
        g = f + g;
        f = g - f;
    }
    return f == 0 ? 0 : g;
}

解法3

既然已经知道本题实际上就是求解斐波那契数列,那么可以利用矩阵的快速幂求解

实现代码

// 矩阵乘法
public int[,] matrixMul(int[,] m1, int[,] m2)
{
    int[,] ret = {
        {m1[0, 0] * m2[0,0] + m1[0, 1] * m2[1,0], m1[0, 0] * m2[0,1] + m1[0, 1] * m2[1,1]}, 
        {m1[1, 0] * m2[0,0] + m1[1, 1] * m2[1,0], m1[1, 0] * m2[0,1] + m1[1, 1] * m2[1,1]}
    };
    return ret;
}

// 矩阵快速幂
public int[,] matrixPow(int[,] m, int n)
{
    int[,] ret = { { 1, 0 }, { 0, 1 } };
    while (n > 0)
    {
        if ((n & 1)> 0){
            ret = matrixMul(ret, m);
        }
        n >>= 1;
        m = matrixMul(m, m);
    }
    return ret;
}

public int rectCoverOptimize2(int number)
{
    if (number == 0)
        return 0;
    int[,] unit = { { 1, 1 }, { 1, 0 } };
    int[,] ret = matrixPow(unit, number);
    int[,] m = { { 1, 0 }, { 0, 0 } };
    ret = matrixMul(ret, m);
    return ret[0,0];
}
06-13 00:50