动态规划法面试题（一）：矩形覆盖

关于矩形覆盖面试题

　　之前已经在上一篇分治法面试题（一）：矩形覆盖一文中给出了该问题的递归解法。但是上面的分析可以看出效率不高，主要是存在大量重复元素的计算。那么如何避免大量重复元素的计算呢？这里将给出几种解决方案。

关于动态规划

　　动态规划的思想与我们上篇探讨的分治法相似，也是通过组合子问题的解从而得到整个问题的解。从上节给出的题目看得出来，分治分解出的子问题都是相对独立的，但是动态规划分解的子问题通常不是独立存在的。分治法有时候存在分解后的问题太多，因而重复计算也多的问题。那么如果能够保存已求得的子问题的答案，从而在再次使用的时候调出，就会节省大量的时间。我们可以用一个表（数组）来存放求得的子问题的解，这就是动态规划的思想。

　　下面就给出集中解决方案，题目仍采用上篇所述的矩形覆盖。

解决方案1

class Solution {
public:
    int a[1000];//采用动态数组更好，此处仅作演示
    int rectCover(int number) {
        if(a[number]!=0)
            return a[number];
        if(number<=0) return 0;
        if(number==1) a[number]=1;
        else if(number==2) a[number]=2;
        else
            {
            int p=rectCover(number-1);
            int q=rectCover(number-2);
            a[number]=p+q;
        }
        return a[number];
    }
};

　　该解法称为动态规划的“备忘录”法，即带备忘的自顶向下法。感兴趣的可以拿上篇分析的rectCover(5)来试试，rectCover(1),rectCover(2)都只需要计算一次。即如果该元素已经被计算过了，那就直接“取”。

解决方案2

 1 class Solution {
 2 //自底向上
 3 public:
 4     int a[1000];
 5     int rectCover(int number) {
 6        a[1]=1;
 7         a[2]=2;
 8         for(int i=3;i<=number;i++)
 9             a[i]=a[i-1]+a[i-2];
10         return a[number];;
11     }
12 };

　　事实上，解法一是动态规划的变形形式，动态规划一般的都是自底向上求解，如解法2。

解决方案3

 1 class Solution {
 2 public:
 3     int rectCover(int number) {
 4       if(number<=0) return 0;
 5         if(number==1) return 1;
 6         if(number==2) return 2;
 7         int num1=1;
 8         int num2=2;
 9         int result=0;
10         number=number-2;
11         while(number--){
12             result=num1+num2;
13             num1=num2;
14             num2=result;
15         }
16         return result;
17     }
18 };

　　解决方案3的最大的优势是不需要额外的数组来存放元素。