LeetCode 790 多米诺和托米诺平铺 题解

对于本题不去看LeetCode的评论区和题解很难想到如何去dp，毕竟就算再怎么枚举也很难找到适用于面向结果的规律。所以对于题解我建议大家还是去看一下灵神给的题解，以下是灵神汇总的图，如果能看懂的话，对于解决题目有很大的帮助。

根据图中所示我们便能找到规律了

n=0 1  
n=1 1
n为2 => 2 = 1* 2+0  
n为3 => 5 = 2* 2+1  
n为4 => 11 = 5* 2+1  
n为5 => 24 = 11* 2+2  
n为6 => 53 = 24* 2+5  
n为7 =>117 = 53* 2+11  
n为8 => 258 = 117* 2+24  
n为n =>??? = dp[n-1]* 2+dp[n-2-1]

然后根据题目要求，我们还需要mod，所以最后的解题步骤如下所示

class Solution {private static final int MOD = 1_000_000_007;public int numTilings(int n) {if (n == 1) {return 1;}long[] f = new long[n + 1];f[0] = f[1] = 1;f[2] = 2;for (int i = 3; i <= n; i++) {f[i] = (f[i - 1] * 2 + f[i - 3]) % MOD;}return (int) f[n];}}