题目描述 我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?
思路:爬楼梯的变种。
Java代码:
public class Solution {
static int[] dp = new int[10000];
public int RectCover(int target) {
if ( target == 1){
dp[target] = 1;
return dp[target];
}else if(target == 2){
dp[target] = 2;
return dp[target];
}else{
for ( int i = 3 ; i <= target ; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[target];
}
}
}
C++代码
class Solution {
public:
int data[100000];
int rectCover(int number) {
if(number == 1){
data[number] = 1;
}
if(number == 2){
data[number] = 2;
}
for(int i = 3 ; i <= number ; i++){
data[i] = data[i-2]+data[i-1];
}
return data[number];
}
};