Jz-010 – Rectangular overlay

The rectangle cover

Topic describes

We can cover a larger rectangle with a smaller rectangle of 21 horizontal or vertical. How many ways are there to cover a 2* N rectangle with n small rectangles of 21 without overlapping?

Title link: Rectangle overlay

code

/** ** * We can cover a larger rectangle with a 2*1 rectangle horizontally or vertically. How many ways are there to cover a large 2* N rectangle with n small 2*1 rectangles without overlapping? * 
 * For example, if n=3, there are three ways to cover a 2*3 rectangle block: * Title link * https://www.nowcoder.com/practice/72a5a919508a4251859fb2cfb987a0e6?tpId=13&&tqId=11163&rp=1&ru=/ta/coding-interviews&qru =/ta/coding-interviews/question-ranking */
public class Jz10 {

    /** * iterative method * method: to cover a large 2* N rectangle, you can first cover the 2*1 rectangle, and then cover the 2*(n-1) rectangle; * or cover the 2 by 2 rectangle first, and then cover the 2 by n minus 2 rectangle. And rectangles covering 2 times n minus 1 and 2 times n minus 2 can be considered subproblems. * *@param target
     * @return* /
    public static int rectCover(int target) {
        if (target <= 2) {
            return target;
        }
        int first = 1, second = 2;
        for (int i = 3; i <= target; i++) {
            second = second + first;
            first = second - first;
        }
        return second;
    }

    public static void main(String[] args) {
        for (int i = 1; i < 10; i++) { System.out.println(rectCover(i)); }}}Copy the code

【 Daily message 】 Idle to see flowers, waiting for flowers to fall, lengnuanzizhi, clean as the beginning.