【墨染】找特有姿态！基于【灵茶山艾府】题解的补充图解

脑筋急转弯

补充证明 灵茶山艾府找不到规律？请看图！（Python/Java/C++/Go）
一定要看链接里的图！本题为看图的形象证明！！

定义: $dp[n]$ 是 $2\times n$ 矩形的 所有姿态 组成的状态。
一般规律：对于 $i+j=n$ , $dp[n]$ 包含 $dp[j]$ 拼接 在 $dp[i]$ 后组成的任何姿态。
如：$n=4$ ，$dp[4]$ 包含 $dp[1]$ 拼接在 $dp[3]$ 后组成的任何姿态。

在链接中，找到新规律。从 $dp[3]$ 开始，每一个新状态都会多出两种 特有姿态 。
特有姿态 $sp[i]$ 定义:不由之前状态拼接的全新姿态。
特有姿态如下：

观察，记录 $dp[i]$ 对应的特有姿态 $sp[i]$，有
①$sp[1]=sp[2]=1$
②$sp[3]=sp[4]=\cdots =sp[n]=2$

对于 $i+j=n$ ，遍历 $i=n-1,n-2,n-3,\dots ,2,1$ ; $j=1,2,3,\dots ,n-2,n-1$ ，将 $j$ 的特有姿态 $sp[j]$ ，拼接在 $i$ 的所有姿态 $dp[i]$ 后，就可以 不重不漏 的组成 $n$ 的所有姿态 $dp[n]$ 。

数学证明，可以略过，看结论

(可以不看)得到递推式 ③$dp[n]=dp[n-1]\times sp[1]+dp[n-2]\times sp[2]+dp[n-3]\times sp[3]+\cdots +dp[1]\times sp[n-1]$。
①②代入③，得 $dp[n]=dp[n-1]+dp[n-2]+2\times dp[n-3]+2\times dp[n-4]+\cdots +2\times dp[1]$
整理,得 ④$dp[n]=dp[n-1]+dp[n-2]+2\times (dp[n-3]+dp[n-4]+\cdots +dp[1])$
又⑤$dp[n-1]=dp[n-2]+dp[n-3]+2\times (dp[n-4]+dp[n-5]+\cdots +dp[1])$

结论

④-⑤,得 $dp[n]-dp[n-1]=dp[n-1]+dp[n-3]$
结论: $dp[n]=2\times dp[n-1]+dp[n-3]$

思考过程，可以不看

(可以不看) 对于 $i+j=n$ ，遍历 $i=n-1,n-2,n-3,\dots ,2,1$ 一定有 $j=1,2,3,\dots ,n-2,n-1$ ,将 $dp[j]$ 拼接在 $dp[i]$ 后，组成 $n$ 的所有姿态 $dp[n]$。差在包含重复姿态，好在包含所有姿态。对这一步优化，发现了特有姿态 $sp$。

class Solution {
public:
    int numTilings(int n) {
        long long dp[n+10];
        int mod = 1e9+7;
        memset(dp,0,sizeof dp);
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3;i<=n;i++) dp[i] = (2*dp[i-1] + dp[i-3])%mod;
        return dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度 : $O(n)$ 。
空间复杂度 : $O(n)$ 。