【2错-2】矩形覆盖

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|尾递归实现有点问题|

题目:我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个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);
    }
}

你可能感兴趣的