Leetcode 2320. 统计放置房子的方式数

原题链接：. - 力扣（LeetCode）

一条街道上共有 n * 2 个 地块 ，街道的两侧各有 n 个地块。每一边的地块都按从 1 到 n 编号。每个地块上都可以放置一所房子。

现要求街道同一侧不能存在两所房子相邻的情况，请你计算并返回放置房屋的方式数目。由于答案可能很大，需要对 109 + 7 取余后再返回。

注意，如果一所房子放置在这条街某一侧上的第 i 个地块，不影响在另一侧的第 i 个地块放置房子。

示例 1：

输入：n = 1
输出：4
解释：
可能的放置方式：
1. 所有地块都不放置房子。
2. 一所房子放在街道的某一侧。
3. 一所房子放在街道的另一侧。
4. 放置两所房子，街道两侧各放置一所。

示例 2：

输入：n = 2
输出：9
解释：如上图所示，共有 9 种可能的放置方式。

提示：

• 1 <= n <=

思路：

考虑单侧的方案数。定义 f [ i ] 为 前 i 个地块的放置方案数。在第 i 个地块处，有放置与不放置两种选项。一、若选择放置，则 第 i -1 个地块不能放置，第 i -2 个地块可以放置也可以不放置，故 此时 前 i 个地块的放置方案数等于前 i -2 个地块的放置方案数。即 f [ i ] = f [ i- 2]。二、若选择不放置，则第 i -1 个地块处可放置也可不放置，前 i 个地块的放置方案数等于前 i -1 个地块的放置方案数，即 f [ i ] = f [ i - 1]。由于 在第 i 个地块处有两种选择，不同的选择带来的结果的总和是前 i 个地块的放置方案数总和。所以 f [ i ] = f [ i -1] + f[ i -2]。

初始化时，f [ 0 ] = 1，0 块地的时候不放也是一种方案。 f [ 1 ] = 2，一块地的时候有 放与不放两种方案。遍历顺序：由于   f [ i ] = f [ i -1] + f[ i -2]，所以 要从前往后遍历。

由于两侧的方案数 f(n) 是独立的，则最后结果为 f(n) * f(n)。

代码：

class Solution {
    private static final int mod = (int)1e9 + 7;
    public int countHousePlacements(int n) {
        //f[i]表示单侧前i个地块的放置方案数
        int[] f = new int[n+1];
        f[0] = 1;
        f[1] = 2;
        for(int i=2;i<=n;i++){
            //在第i个地块处，可放可不放
            //如果不放，则第 i-1 块可放可不放，f[i]=f[i-1];
            //如果放，则第i-1块不可放，第i-2块可放可不放，f[i]=f[i-2]
            f[i] = (f[i-1]+f[i-2]) % mod;
        }
        return (int)((long)f[n]*f[n] % mod);
    }
}

参考：. - 力扣（LeetCode）

原文地址：https://blog.csdn.net/fujiang_xiao/article/details/142612799

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！