关于#小池注水#的问题，如何解决？

Question

题目名称：水池注水
题目描述
给定nn水池。 向nn水池中注水。 每行每列只能注水一个方格。 如果一个方格的四周有两个方格已经注水，则该方格也会被水覆盖。 小Q想知道自己有多少种方案可以使得自己的水池被完全覆盖。

输入描述：
给定整数n。(1<=n<=1e5)

输出描述：
输出方案数，对1e9+7取模。

示例

示例1
输入
4

输出
22

Answer 1

#include <iostream>
using namespace std;
const int mod = 1e9 + 7;
int f[100005][3];
int main()
{
    int n;
    cin >> n;
    f[0][0] = 1;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            f[j][0] = (f[j-1][0] + f[j-1][1] + f[j-1][2]) % mod;
            f[j][1] = (f[j-1][0] + f[j-1][2] + f[j][j-1][0] + f[j][j-1][2]) % mod;
            f[j][2] = (f[j-1][1] + f[j][j-1][1] + f[j-1][j-1][2]) % mod;
        }
    }
    cout << f[n][2] << endl;
    return 0;
}