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

利用动态规划,一共有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];
}
}

  

上一篇:Linux 环境进程间通信(六):


下一篇:Lisp学习:这是本质与应用?