利用动态规划,一共有n列,若从左向右放小矩形,有两种放置方式:
第一种:横着放,即占用两列。此时第二行的前两个空格只能横着放,所有,总的放置次数变为1+num(2*(n-2)),其中2*(n-2)代表两行n-2列的矩阵
第二种:竖着放,此时有1+num(2*(n-1)),因此 利用动态规划求解 public class Solution {
public int RectCover(int target) {
int [] res = new int[target+1];
if(target<=2){
return target;
}
res[0]=0;
res[1]=1;
res[2]=2;
for(int i=3;i<=target;i++){
res[i] = res[i-1]+res[i-2];
}
return res[target];
}
}