Java教程

JZ10 矩形覆盖

本文主要是介绍JZ10 矩形覆盖，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

原题链接


描述

我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，从同一个方向看总共有多少种不同的方法？


示例

输入：4
返回值：5

思路

从头开始递推，2*1 只有一种，2*2有两种（全横向或者全纵向），2*3有3种，这样很容易总结出：2*n的大矩形的覆盖方法是2*(n-1) 和2*(n-2)的覆盖方法数之和。


解答

public class Solution {
    public int rectCover(int target) {
        if (target <= 2) return target;
        int res = 0;
        int pre1 = 1, pre2 = 2;
        for (int i = 3; i <= target; i++) {
            res = pre1 + pre2;
            pre1 = pre2;
            pre2 = res;
        }
        return res;
    }
}
这篇关于JZ10 矩形覆盖的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航