【动态规划】矩形覆盖

1. 题目描述

假设我们可以用如图1所示21的小矩形横着或者竖着去覆盖更大的矩形，请问用8个21的小矩形去无重复的覆盖一个2*8的大矩形。总共有多少种方法。

2.算法分析

这道题出自《剑指offer》，也是一道考察动态规划的基础题。把覆盖28矩形的覆盖方法总数记为f(8).用第一个矩形去覆盖大矩形时，有两种选择，横放或者竖放。竖放时，右边有27的区域尚未被覆盖，那么剩下区域覆盖方法的总数为f(7)。第一个矩形横向的情况下，必须占用另外一个小矩形去覆盖左下角。因此右边还剩下2*6的区域尚未被覆盖，记为f(6)。因此可以得出关系， f(8) = f(7) + f(6)。显然我们也知道f(1)=1,f(2) = 2.可以写出代码：

3. 实现1

#include<iostream>
using namespace std;
int covercnt(int n);
int main()
{
    int n;
    cin >> n;
    cout << covercnt(n);
}
int covercnt(int n)
{
    if (n  <= 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 2;
    }
    return covercnt(n - 1) + covercnt(n - 2);    
}

这种实现用递归实现，当输入的n值稍微大一点，那么递归调用层次会很深，执行起来特别慢。仔细分析这个执行过程我们发现，重复的计算实在是太多了，比如计算f(8)，必须先计算f(7)和f(6),计算f(7)的时候又要计算一次f(6)，计算的中间结果不能复用，那么我们可以改进一下，开一个数组来保存中间结果，当需要计算f(n)时，首先查询数组中是否已经计算过了f(n)的值，如果有，那么不必重复计算，直接用，如果没有，那么计算一次，把计算结果保存到数组中。这是第一种方法，这种方法的好处就是已空间换时间，坏处就是，当需要计算的n值很大时，会很耗空间，同时，用户输入的n值不能提前预估大小，因此不能确定需要的数组长度。第二种方法是，自底向上来计算，比如计算f(8)的时候，我们从f(1)、f(2)开始算起，有了f(1)、f(2)的值就好计算f(3)了，有了f(2)、f(3)就好计算f(4)了，依次类推，很快可以计算出f(8)来。且看算法实现2.

4. 实现2

int covercnt(int n)
{
   int a , b , tmp = 0;
   if (n <= 0) {
       return 0;
   } else if (n == 1) {
       return 1;
   } else if (n == 2) {
       return 2;
   }
   a = 1; // a = f(1)
   b = 2; // b = f(2)
   n -= 2; // 从3开始计算
   while (n) {
       tmp = a + b;
       a = b;
       b = tmp;
       n--;
   }
   return tmp;
}

这种算法是比较理想的算法