[toc]

题目描述

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

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

思路以及解法

先说思路,基本是递归,首先如果n为1,那么肯定只有一种,f(1)=1,如果n=2,f(2)=2

但是n>2的时候呢?那么我们的思路就可以分为第一次切分长度为1,和切分长度为2来计算,也就是剩下的是f(n-1)和f(n-2),两者加起来即可。
$$f(n)=\begin




f(n-1)+f(n-2),n>2
\end0,n<=0\1,n=1\2,n=2\

$$

递归写法代码如下:

public class Solution {
    public int RectCover(int target) {
        if(target<=0){
            return 0;
        }else if(target==1){
            return 1;
        }else if(target==2){
            return 2;
        }else {
            return RectCover(target-1)+RectCover(target-2);
        }
    }
}

如果我不想使用递归呢?
那么直接不断地把前面两个数加起来赋值给当前的数字即可。

public class Solution {
    public int RectCover(int target) {
        if (target <= 0) {
            return 0;
        } else if (target < 3) {
            return target;
        } else {
            int num1 = 1;
            int num2 = 2;
            int result = 0;
            for (int i = 3; i <= target; i++) {
                result = num1 + num2;
                num1 = num2;
                num2 = result;
            }
            return result;
        }
    }
}

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

纵然缓慢,驰而不息。