10.剑指offer-矩形覆盖

时间:2022-11-22 07:22:58


题干

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

我的思路

没思路,直接看的答案。
这对这种情况,是应用问题抽象成数学问题的功底太差了。不要凭空想,写一写效果会更好。

大佬解析

10.剑指offer-矩形覆盖


10.剑指offer-矩形覆盖


10.剑指offer-矩形覆盖

public class Solution {
public int RectCover(int target) {
if (target <= 2){
return target;
}
int pre1 = 2; // n 最后使用一块,剩下 n-1 块的写法
int pre2 = 1; // n 最后使用两块,剩下 n-2 块的写法
for (int i = 3; i <= target; i++){
int cur = pre1 + pre2;
pre2 = pre1;
pre1 = cur;
}
return pre1; //相对于 n+1 块来说,第 n 种的方法
}
}

总结

为什么做不出来呢?
首先没有仔细的读题,脑子里想的需要覆盖的图像的形状不对。
一定要学会抽象数学问题,学会从应用问题中抽取出模型来。