https://www.nowcoder.com/practice/72a5a919508a4251859fb2cfb987a0e6?tpId=13&tqId=11163&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
| 日期 | 是否一次通过 | comment |
|----|----|----|
|2019-01-26 13:20|N|实质是斐波那契数列，尾递归实现有点问题|
|2019-01-27 13:20|N|尾递归实现有点问题|
题目：我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
1. 递归
public class Solution {
public int RectCover(int target) {
if(target <= 2) {
return target;
}
return helper(target);
}
private int helper(int target) {
if(target <= 2) {
return target;
}
return helper(target-1)+helper(target-2);
}
}
2.尾递归
public class Solution {
public int RectCover(int target) {
if(target <= 2) {
return target;
}
return helper(target, 1, 2);
}
private int helper(int target, int num1, int num2) {
if(target == 1) {
return num1;
}
return helper(target-1, num2, num1+num2);
}
}
