※ 引述《yam276 (史莱哲林的优等生)》之铭言：
: 790. Domino and Tromino Tiling
: https://leetcode.com/problems/domino-and-tromino-tiling/
: 题意：
: 你有2x1跟L型的多米诺
: 能拼出几种2xn的矩阵
我想到的解法是只用一维的dp，
具体思路是把每一次dp得到的数字都设为此时有几种2*i的骨牌组合，
并设2*0为1种，
不过时间复杂度就会高一点
例如2*1矩形有1种组合，
2*2矩形可以是2*1矩形再加上1个竖直摆放的长方形骨牌，
或从头开始摆2个横向摆放的长方形骨牌，
结果是1+1=2种
2*3矩形则是除2*2矩形加1个直骨牌与2*1矩形加2个横骨牌之外，
还可以从头开始摆2个L形骨牌，有2种摆法
结果是2+2+1=5种
归纳结果，
如果当前要组2*i的矩形，
在i>2的情况下，
其组合总数是dp[0:i-2] * 2 + dp[i-2] + dp[i-1]种

你这样不如prefix sum用扣的

确实，不过还好题目给的范围允许时间复杂度n^2

酷