题目描述：一条街道上共有 n * 2 个地块 ，街道的两侧各有 n 个地块。每一边的地块都按从 1 到 n 编号。每个地块上都可以放置一所房子。现要求街道同一侧不能存在两所房子相邻的情况，请你计算并返回放置房屋的方式数目。由于答案可能很大，需要对 109 + 7 取余后再返回。

方法1：动态规划dp[i]表示n个地块时可放置的房屋数，有两种情况：

第i个地块不放，dp[i-1]种，第i个地块放，dp[i-2]种，dp[i] = dp[i-1]+dp[i-2]

class Solution {
public:
    int countHousePlacements(int n) {
        vector<int>dp(n+1);
        dp[0] = 1;
        dp[1] = 2;
        int a = 1e9 + 7;
        for(int i=2;i<=n;i++){
            dp[i] = (dp[i-1] + dp[i-2])%a;
        }
        return (dp[n] * dp[n])%a;

    }
};

出现错误，内存溢出

错误原因，dp[n] * dp[n]这个值可能会溢出，将dp数组设为long int

class Solution {
public:
    int countHousePlacements(int n) {
        vector<long int>dp(n+1);
        dp[0] = 1;
        dp[1] = 2;
        int a = 1e9 + 7;
        for(int i=2;i<=n;i++){
            dp[i] = (dp[i-1] + dp[i-2])%a;
        }
        return (dp[n] * dp[n])%a;

    }
};

不用dp数组，记得把s设为long int

class Solution {
public:
    int countHousePlacements(int n) {
        int p = 1;
        int q = 2;

        long int s = 2;
        int a = 1e9 + 7;
        for(int i=1;i<n;i++){
            s = (p + q)%a;
            p = q;
            q = s;
        }
        return (s * s)%a;

    }
};