題目描述

我們可以用2*1的小矩形橫著或者豎著去覆蓋更大的矩形。請(qǐng)問(wèn)用n個(gè)2*1的小矩形無(wú)重疊地覆蓋一個(gè)2*n的大矩形，總共有多少種方法？

?

?思路如下:

?

• 當(dāng)?shù)谝淮螜M著覆蓋時(shí)，覆蓋方法為f(n-2);
• 當(dāng)?shù)谝淮呜Q著覆蓋時(shí)，覆蓋方法為f(n-1);
• 因此f(n)=f(n-1)+f(n-2);
• 當(dāng)n=1時(shí)，只有1種覆蓋方法，當(dāng)n=2時(shí)，有2種覆蓋方法。
• 此題最終得出的仍然是一個(gè)斐波那契數(shù)列。
• n=1, f(n)=1
  n=2, f(n)=2
  n>2,且為整數(shù), f(n)=f(n-1)+f(n-2)

package com.jianzhioffer;public class RectCover {public static void main(String[] args){int res = rectCover(15);System.out.println(res);res = rectCoverByFor(15);System.out.println(res);}// 遞歸public static int rectCover(int target){if(target == 0){return 0;}if(target == 1){return 1;}if(target == 2){return 2;}return rectCover(target-1)+rectCover(target-2);}// for循環(huán)public static int rectCoverByFor(int target){if(target<=2)return target;int[] num = new int[target];num[0] = 1;num[1] = 2;for(int i=2;i<target;i++){num[i] = num[i-1] + num[i-2];}return num[target-1];} }

?

?

總結(jié)

以上是生活随笔為你收集整理的剑指offer十:矩形覆盖的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。