790. 多米诺和托米诺平铺 - 力扣（LeetCode）

在力扣 App 中打开

调试中...

题目描述

题解

提交记录

代码

测试用例

测试结果

790. 多米诺和托米诺平铺

中等

相关企业

💡 讨论区规则

1. 请不要在评论区发表题解！

2. 评论区可以发表关于对翻译的建议、对题目的疑问及其延伸讨论。

3. 如果你需要整理题解思路，获得反馈从而进阶提升，可以去题解区进行。

malog_

2025.04.03

矩阵快速幂

class Solution {
public:
    int mod = 1e9+7;

    vector<vector<long long>> multiply(const vector<vector<long long>>& a, const vector<vector<long long>>& b) {
        int n = a.size();
        int m = b[0].size();
        int k = a[0].size();
        vector<vector<long long>> ans(n, vector<long long>(m));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                for (int c = 0; c < k; c++) {
                    ans[i][j] = (int)(((long long)a[i][c] * b[c][j] + ans[i][j]) % mod);
                }
            }
        }
        return ans;
    }

    vector<vector<long long>> power(vector<vector<long long>> m, int p) {
        int n = m.size();
        vector<vector<long long>> ans(n, vector<long long>(n));
        for (int i = 0; i < n; i++) {
            ans[i][i] = 1;
        }
        for (; p != 0; p >>= 1) {
            if ((p & 1) != 0) {
                ans = multiply(ans, m);
            }
            m = multiply(m, m);
        }
        return ans;
    }

    int f2(int n)
    {
        if(n == 0)
        {
            return 1;
        }
        if(n == 1)
        {
            return 2;
        }
        if(n == 2)
        {
            return 5;
        }

        vector<vector<long long>> start = { {5, 2, 1} };
        vector<vector<long long>> base = { {2, 1, 0} , {0, 0, 1} , {1, 0, 0} };
        vector<vector<long long>> ans = multiply(start, power(base, n - 2));
        return ans[0][0];
    }    

    int numTilings(int n) {
        return f2(n - 1);
    }
};

文件传输助手

2025.02.25

左下角有向上的拇指，为什么没有向下的呢？

老宋🐾

2022.11.11

解这道题的第一步，是把题目翻译成人话。下面这一段，我表示不属于人话：

平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同，当且仅当面板上有四个方向上的相邻单元中的两个，使得恰好有一个平铺有一个瓷砖占据两个正方形。

看了一下英文版，我表示英文版不但不属于人话，也不属于地球上任何一种鸟语：

In a tiling, every square must be covered by a tile. Two tilings are different if and only if there are two 4-directionally adjacent cells on the board such that exactly one of the tilings has both squares occupied by a tile.

不想做了，一读使人烦，二读使人躁，三读使人想摔电脑。

167

ydnacyw

2023.11.18

先点开评论，再点开题解

...

2022.11.12

面向答案编程：
if(n==1) return 1;if(n==2) return 2;if(n==3) return 5;if(n==4) return 11;if(n==5) return 24;if(n==6) return 53;if(n==7) return 117;if(n==8) return 258;if(n==9) return 569;if(n==10) return 1255; if(n==20) return 3418626;if(n==30) return 312342182;if(n==40) return 833773577;if(n==50) return 451995198;if(n==60) return 882347204;if(n==70) return 155521223;if(n==80) return 621192477;if(n==90) return 632727593; if(n==100) return 190242381;if(n==119) return 853328156; if(n==211) return 374315309;if(n==232) return 25197135;if(n==262) return 718490430; if(n==428) return 401892698;if(n==449) return 288656278; if(n==500) return 603582422;if(n==574) return 461429539; if(n==630) return 189827198;if(n==668) return 218895443;if(n==694) return 74178564;if(n==699) return 939053561; if(n==700) return 637136622;if(n==728) return 217951151;if(n==758) return 446953183; if(n==802) return 473826217;if(n==814) return 443572580;if(n==829) return 969408247;if(n==865) return 305566409; if(n==951) return 326538883; if(n==1000) return 979232805; return 0;

可爱抱抱呀😥

2022.11.11

这道题来自：Weekly Contest 73，，类似于这样的当前的多种状态，只跟前一个状态的多种状态成线性关系的，可以用矩阵来表示它的系数然后动态规划，是否一定需要利用快速幂取决于每个时刻状态数的多少以及求得时刻是多少

无优化的动态规划，四种状态：00：最后一列都没铺，01：最后一列只铺了下边，10：最后一块只铺了上边，11：最后一列铺满了，，这里为了图省事，把系数写在了矩阵里：

/*
@可爱抱抱呀
执行用时：2 ms, 在所有 Java 提交中击败了29.68%的用户
内存消耗：39.2 MB, 在所有 Java 提交中击败了7.74%的用户
2022年11月11日 17:33
*/
class Solution {
    int mod=(int)1e9+7,matrix[][]={{0,1,1,1},{0,0,1,1},{0,1,0,1},{1,0,0,1}}; 
    public int numTilings(int n) {
        long ans[][]=new long[n][4];
        ans[0]=new long[]{1,0,0,1};
        for(int i=1;i<n;i++){
            for(int j=0;j<4;j++){
                for(int k=0;k<4;k++){ans[i][j]+=ans[i-1][k]*matrix[k][j];}
                ans[i][j]%=mod;
            }
        }
        return (int)ans[n-1][3];
    }
}

滚动数组优化空间：

/*
@可爱抱抱呀
执行用时：2 ms, 在所有 Java 提交中击败了29.68%的用户
内存消耗：39.2 MB, 在所有 Java 提交中击败了5.16%的用户
2022年11月11日 17:39
*/
class Solution {
    int mod=(int)1e9+7,matrix[][]={{0,1,1,1},{0,0,1,1},{0,1,0,1},{1,0,0,1}}; 
    public int numTilings(int n) {
        long ans[]=new long[]{1,0,0,1};
        for(int i=1;i<n;i++){
            long arr[]=new long[4];
            for(int j=0;j<4;j++){
                for(int k=0;k<4;k++){arr[j]+=ans[k]*matrix[k][j];}
                arr[j]%=mod;
            }
            ans=arr;
        }
        return (int)ans[3];
    }
}

矩阵快速幂：

/*
@可爱抱抱呀
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：38.3 MB, 在所有 Java 提交中击败了78.71%的用户
2022年11月11日 19:34
*/
class Solution {
    long mod=(int)1e9+7,matrix[][]={{0,1,1,1},{0,0,1,1},{0,1,0,1},{1,0,0,1}}; 
    public int numTilings(int n) {
        long ans[]=new long[]{1,0,0,1};
        n--;
        while(n>0){            
            if(n%2==1){
                long arr[]=new long[4];
                for(int j=0;j<4;j++){
                    for(int k=0;k<4;k++){arr[j]+=ans[k]*matrix[k][j];}
                    arr[j]%=mod;
                }
                ans=arr;
            }            
            matrix=square();
            n>>=1;
        }
        return (int)ans[3];
    }
    long[][] square(){
        long ans[][]=new long[4][4];
        for(int i=0;i<4;i++){
            for(int j=0;j<4;j++){
                for(int k=0;k<4;k++){ans[i][j]+=matrix[i][k]*matrix[k][j];}
                ans[i][j]%=mod;
            }
        }
        return ans;
    }
}

当然数据量不大，可以直接打表：

/*
@可爱抱抱呀
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：38.6 MB, 在所有 Java 提交中击败了54.19%的用户
2022年11月11日 19:51
*/
class Solution {
    int ans[]={1,2,5,11,24,53,117,258,569,1255,2768,6105,13465,29698,65501,144467,318632,702765,1549997,3418626,7540017,16630031,36678688,80897393,178424817,393528322,867954037,914332884,222194076,312342182,539017241,300228551,912799284,364615795,29460134,971719552,308054885,645569904,262859346,833773577,313117044,889093434,611960431,537037899,963169225,538298867,613635626,190440463,919179793,451995198,94430852,108041490,668078178,430587201,969215892,606509948,643607090,256430058,119370057,882347204,21124452,161618961,205585119,432294690,26208334,258001787,948298264,922804855,103611483,155521223,233847294,571306071,298133358,830114010,231534077,761201512,352517020,936568117,634337732,621192477,178953057,992243846,605680155,390313360,772870559,151421259,693155878,159182301,469785861,632727593,424637480,319060814,270849214,966335908,251732616,774314446,514964786,281662181,337638801,190242381,662146943,661932680,514107734,690362404,42657474,599422682,889207761,821072989,241568646,372345046,565763074,373094787,118534613,802832300,978759380,76053359,954939018,888637402,853328156,661595316,211828020,276984189,215563687,642955394,562894970,341353620,325662627,214220217,769794054,865250728,944721666,659237372,183725458,312172575,283582515,750890488,813953544,911489596,573869666,961692869,834875320,243620292,448933446,732742205,709104695,867142829,467027849,643160386,153463587,773955023,191070418,535604423,845163862,881398135,298400679,441965213,765328554,829057780,100080759,965490072,760037910,620156572,205803202,171644307,963445186,132693560,437031427,837508033,807709619,52450651,942409335,692528275,437507194,817423716,327375693,92258573,1940855,331257403,754773379,511487606,354232608,463238588,437964775,230162151,923562890,285090541,800343233,524249342,333589218,467521662,459292659,252174529,971870720,403034085,58242692,88356097,579746279,217735243,523826583,627399438,472534112,468894800,565189031,602912167,674719127,914627278,432166709,539052538,992732347,417631389,374315309,741362958,900357298,175029891,91422733,83202757,341435405,774293543,631789836,605015070,984323676,600437174,805889411,596102484,792642135,391173667,378449811,549541750,490257160,35***124,267469991,25197135,409358394,86186772,197570679,804499752,695186269,587943210,980386165,655958585,899860373,780106897,216172365,332205096,444517082,105206522,542618140,529753355,164713225,872044590,273842521,712398267,296841110,867524741,447447735,191736573,250997880,949443495,90623549,432244978,813933444,718490430,869225831,552385092,823260607,515747031,583879147,991018894,497784805,579448750,149916380,797617565,174683866,499284112,796185782,767055423,33394944,862975670,493006749,19408435,901792540,296591815,612592065,126976656,550545127,713682312,554341273,659227666,32137630,618616533,***60725,825059073,268734665,433930048,692919162,654572982,743076005,179071158,12715291,768506587,716084325,444883934,658274448,32633207,510150348,678575137,389783474,289717289,258009708,905802890,101323055,460655818,827114519,755552086,971759983,770634471,296821014,565402004,901438472,99697944,764797892,431034242,961766428,688330734,807695703,577157820,842646367,492988423,563134659,968915678,430819765,424774182,818464035,67747821,560269824,939003676,945755166,451780142,842563953,630883058,713546251,269656441,170195933,53938110,377532661,925261255,904460613,186453873,298168994,500798594,188051054,674271102,849340791,886732629,447736346,744813476,376359567,200455473,145724415,667808397,536072260,217868928,103546246,743164752,704198425,511943089,767050923,238300257,988543603,744138115,726576480,441696549,627531206,981638885,404974305,437479809,856598496,118171283,673822375,204243232,526657747,727137862,658518949,843695638,414529124,487577190,818850011,52229132,592035454,2920905,58070942,708177338,419275574,896622090,501421504,422118575,740859233,983139963,388398487,517656200,18452349,425303185,368262563,754977475,935258128,238778805,232535078,400328277,39435352,311405782,23139834,85715020,482835822,988811478,63337962,609511746,207834956,479007874,567527487,342889923,164787713,897102913,137095735,438979183,775061272,687218272,813415720,401892698,491003661,795423035,992738761,476481169,748385366,489509479,455500120,659385599,808280670,72061446,803508491,415297638,902656722,608821921,632941473,168539654,945901229,524743917,218027481,381956184,288656278,795340037,972636251,233928766,263197562,499031368,231991495,727180552,953392465,138776411,4733367,962859199,64494795,133722957,230305106,525105007,183932964,598171034,721447068,626827093,851825213,425097480,477022046,805869298,36836062,550694170,907257631,851351317,253396790,414051204,679453718,612304219,638659635,956772981,525850167,690359962,337492891,200835942,92031839,521556569,243949073,579929985,681416532,606782130,793494238,268404994,143592111,80678453,429761900,3115904,86910261,603582422,210280741,507471743,618525901,447332536,402136808,422799510,292931549,987999906,398799308,90530158,169060215,736919738,564369627,297799462,332518655,229406930,756613322,845745292,920897507,598408322,42561922,6021344,610451010,263463935,532949214,676349431,616162790,765274787,206898991,29960765,825196317,857291618,744543994,314284291,485860193,716264373,746813030,979486246,675236851,97286718,174059675,23356194,143999106,462057887,947471968,38943028,539943943,27359840,93662708,727269359,481898551,57459803,842188965,166276467,390012737,622214432,410705324,211423378,45061181,500827686,213078743,471218667,443265013,99608762,670436191,784137388,667883531,6203239,796543866,260971249,528145737,852835333,966641908,461429539,775694404,518030702,497490936,770676269,59383226,616257388,3191031,65765288,747787964,498766952,63299185,874386334,247539606,558378397,991143121,229825834,18030058,27203230,284232294,586494646,200192515,684617324,955729287,111651075,907919474,771568221,654787510,217494480,206557174,67901851,353298182,913153538,894208920,141716008,196585547,287380007,716476022,629537584,546455168,809386351,248310272,43075705,895537761,39385780,121847265,139232284,317850348,757547961,654328199,626506739,10561425,675451049,977408830,965379078,606209191,189827198,345033467,296276118,782379434,909792328,115860760,14100947,937994222,991849197,997799334,933592876,859034935,715869190,365331242,589697412,895264007,155859242,901415896,698095785,552050805,5517492,709130769,970312336,946142157,601415069,173142460,292427070,186269202,545680864,383788791,953846784,453374418,290537620,534922017,523218445,336974503,208871016,940960477,218895443,646661902,234284267,687463977,21589842,277463951,242391872,506373586,290211116,822814104,152001780,594214676,11243442,174488664,943192004,897627443,969743543,882679076,662985581,295714691,474108451,611202476,518119636,510347716,631897901,781915431,74178564,780255029,342425475,759029514,298314043,939053561,637136622,572587280,84228107,805592836,183772938,451773983,709140795,602054521,655883018,20906817,643868155,943619321,908145452,460159045,863937404,636020246,732199530,328336450,292693139,317585801,963508052,219709229,757004259,477516556,174742334,106488920,690494396,555731119,217951151,126396691,808524501,835000146,796396976,401318439,637637017,71670996,544660431,726957872,525586733,595833890,918625645,362838009,321509901,561645440,486128882,293767658,149180749,784490380,862748411,874677564,533845494,930439392,735556334,4958148,940355688,616267696,237493533,415342747,446953183,131399892,678142531,803238238,737876361,153895239,111028709,959933779,73762783,258554275,477042322,27847420,314249115,105540545,238928510,792106135,689752808,618434119,28974359,747701526,113837157,256648673,260998865,635834887,528318440,317635738,271106356,70531145,458698028,188502405,447535955,353769931,896042267,239620475,833010881,562064015,363748498,560507870,683079748,729907987,20323830,723727408,177362789,375049408,473826217,125015216,625079840,723985890,572986989,771053811,266093498,105173978,981401767,228897018,562968014,107337781,443572580,450113167,7564108,458700796,367514752,742593612,943888013,255290764,253175133,450238272,155767301,564709735,579657735,315082764,194875256,969408247,253899244,702673744,374755721,3410679,709495102,793745918,590902508,891300111,576346126,743594753,378489603,333325325,410245396,198980388,731286101,872817591,944615563,620517213,113852003,172319562,965156337,44164663,260648888,486454106,17072868,294794624,76043347,169159562,633113748,342270836,853701234,340516202,23303233,900307700,141131588,305566409,511440511,164012603,633591615,778623734,721260064,76111729,930847192,582954434,242020590,414888365,412731157,67482897,549854159,512439468,92361826,734577811,981595083,55551978,845681767,672958603,401469177,648620114,970198824,341866811,332353729,634906275,611679354,555712430,746331128,104341596,764395622,275122358,654586312,73568232,422258822,499103949,71776123,565811068,630726078,333228272,232267605,95261281,523750834,279769266,654799813,833350453,946470165,547740129,928830704,804131559,156003233,240837163,285805878,727614989,696067134,677940139,83495253,863057640,404055405,891606063,646269752,696594902,284795853,215861451,128317797,541431447,298724338,725766473,992964386,284653096,295072658,583109695,450872479,196817609,976744913,404362291,5542184,987829281,380020839,765583862,518996991,418014814,601613483,722223950,862462707,326538883,375301709,613066118,552671112,480643926,574353963,701379031,883401981,341157911,383694846,650791666,642741236,669177311,989146281,621033784,911244872,811636011,244305792,399856449,611348902,467003589,333863620,279076135,25155852,384175324,47426776,120009404,624194132,295815033,711639470,47473058,390761149,493161761,33796573,458354295,409870344,853537261,165428803,740727950,334993147,835415097,411558130,158109400,151633890,714825910,587761213,327156309,369138521,326038248,979232805};
    public int numTilings(int n) {
        return ans[n-1];
    }
}

无福卷毛🇦🇷

2019.07.01

妈呀题都理解不了谁能通俗的翻译下

shsussj

2022.11.12

人话1：两个平铺方案A和B，将A和B进行重叠，如果A中存在至少一个瓷砖覆盖了B中的两个瓷砖，则A和B为不同平铺。

人话2：两个平铺不能完全重叠就是不同的平铺。

（这题干最后一句是人写出来的话吗，建议不要ctrl cv加google translate，题都写不明白）

龅牙叔

2022.07.15

"平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同，当且仅当面板上有四个方向上的相邻单元中的两个，使得恰好有一个平铺有一个瓷砖占据两个正方形。"

这是什么鬼话？

overmind

2022.11.11

每一列就俩格子, 所以有四种形状: 全空, 上满, 下满, 全满
例如想让第i列全空, 则前一列必须全满, 否则第i+1列无法再改变i-1列, 这就有了空缺, 是不允许的.
再比如想让第i列上满, 则

前一列可以是全空, 本列可以加上一个◸骨牌,
前一列也可以是下满, 也就是i-1列上面空一个, 本列可以上面横一条来补满i-1列上空的格, 自己也变成了上满的状态

贡献者

4 人在线

不限

C++JavaPython3CPythonJavaScriptGoC#PHPTypeScriptSwiftRustKotlinScala贪心递归脑筋急转弯记忆化搜索数组数学动态规划状态压缩枚举矩阵数论前缀和滑动窗口模拟

登录并分享题解

・

2022.11.11

多米诺和托米诺平铺

官方

方法一：动态规划考虑这么一种平铺的方式：在第 $i$ 列前面的正方形都被瓷砖覆盖，在第 $i$ 列后面的正方形都没有被瓷砖覆盖（$i$ 从 $1$ 开始计数）。那么第 $i$ 列的正方形有四种被覆盖的情况：一个正方形都没有被覆盖，记为状态 $0$；只有上方的正方形被覆盖，记为状态 $1$；只有下方的正方形被覆盖

Python

动态规划

C++

124

33.3K

178

・

2022.11.11

找不到规律？请看图！（Python/Java/C++/Go）

定义 f[i]f[i]f[i] 表示平铺 2×i2 \times i2×i 面板的方案数，那么答案为 f[n]f[n]f[n]。尝试计算 fff 的前几项，并从中找到规律，得到 f[n]f[n]f[n] 的递推式：代码实现时，可以定义 f[0]=1f[0]=1f[0]=1，这样可以从 f[3]f[3]f[3] 开始算。

Python

数学

动态规划

C++

487

16.9K

・

2022.11.12

【宫水三叶】简单状态机 DP 运用题

状态机 DP 定义 f[i][j] 为无须考虑前 i - 1 列（含义为前 i - 1 列已铺满），当前第 i 列状态为 j 时的方案数。其中 j 取值范围为 [0, 4) 分别对应了当前列的填充情况：为了方便，我们人为规定列数从 1 开始。由于骨牌只能在 2 \times n 的棋盘内填充（不能延伸出棋盘两端

状态机

TypeScript

Python

Java

141

7.1K

・

2025.02.22

矩阵快速幂

Problem: 思路你选用何种方法解题？解题过程这些方法具体怎么运用？复杂度时间复杂度: O(*) 空间复杂度: O(*) Code

C++

矩阵

数学

・

2022.11.12

[Python3/Java/C++/Go] 一题一解：动态规划（详细分析）

方法一：动态规划我们首先要读懂题意，题目实际上是让我们求铺满 2\times n 的面板的方案数，其中面板上的每个正方形只能被一个瓷砖覆盖。瓷砖的形状有两种，分别是 2 x 1 型和 L 型，并且两种瓷砖都可以旋转。我们将旋转后的瓷砖分别记为 1 x 2 型和 L' 型。我们定义 f[i][j] 表示平铺前

Python

Python3

递推

Java

2.6K

・

2024.04.20

动态规划

Problem: 思路使用动态规划的方式解决这个问题。我们要对题目进行抽象和建模，以确定怎样定义状态，怎样进行状态转移。下面的题解记录了我的思考过程。动态规划怎样抽象出状态的本质呢？我有

C++

动态规划

310

・

2024.11.20

[Java/Python3/C++]动态规划+数学：找瓷砖的平铺规律【图解】

790. 多米诺和托米诺平铺题目题目分析思路分析空间优化代码动态规划——数组动态规划——三个变量维护题目有两种形状的瓷砖：一种是 2 x 1 的多米诺形，另一种是形如 "L" 的托米诺形。两种形状都可以旋转。给定整数 n ，返回可以平铺 2 x n 的面板的方法的数量。返回对 1

Python3

Java

C++

动态规划

143

・

2020.06.27

总结一下大佬的dp思路

解题思路受@fireswu的题解启发，详细写写个人做这道题的感受，如有其它高见，请留言讨论。首先说下个人的思路，一开始我一看这个题，联想到的是如果只有多米诺，也就是只有XX这种块块，那就是一个斐波那契数列，用dp[i] = dp[i-1] + dp[i-2]很好解。引入了另一种L型托米诺，如果只有托米诺，那就是

Java

动态规划

3.3K

・

2023.09.14

（动态规划）最简单易懂的状态和代码，时间击败100%用户

思路动态规划定义dp[i][j]表示第i列的状态为j的方案数，j=0或1，其中j=0表示该列全满，j=1表示该列半满，如下图所示：解题方法因为题目中的方块只能跨越两列，所以我们只需考虑状态dp[i] 与 dp[i-1]、dp[i-2]之间的关系，显然：欲使i列全满我们有三种情况：即：欲使i列半满我们也有三种情况

动态规划

330

・

2022.03.13

图解【动态规划】

解题思路依照官方题解思路，推导出简单的递推式s[n] = 2 * s[n - 1] + s[n - 3] s[n]代表当前列都铺满 x[n]代表当前列都不铺 y[n]代表当前列只铺上一行 z[n]代表当前列只铺下一行代码「代码块」

C++

动态规划

1.4K

・

2022.05.30

【yukiyama】790 简单易懂的递推式推导过程

790-多米诺和托米诺平铺 (中等) 解法一：递推式算法描述本方法容易入手，但推导过程需要细心，联立几个式子得到递推式的过程也需要一些耐心。如下，记最后一列，即第 i 列全部铺满，也就是从第 1 列到最后一列全部铺满（只表现最后两列），种类数为 S(i) 「代码块」当最后一列不铺，到第 i - 1 列铺

Java

动态规划

数学

脑筋急转弯

770

・

2022.11.12

前缀和+动态规划

思路定义状态dp[i]表示铺满第i列的方案数初始化dp[0] = 1, dp[1] = 1, dp[2] = 2 preSum表示dp[0] + ...+ dp[i - 3],初始preSum = dp[0] = 1对于dp[i]1.当考虑dp[i]由dp[i-1]递推而来时，需要在dp[i-1]的基础上填补1列 2

C++

前缀和

动态规划

274

・

2019.12.08

找规律

不知道为啥，这里写题解导入不了照片了，就附上博文链接吧，往下翻到这个题，就有对应推导图了。。。题解详细推导图

动态规划

1.7K

・

2022.11.12

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

脑筋急转弯补充证明灵茶山艾府一定要看链接里的图！本题为看图的形象证明！！定义: dp[n] 是 2\times n 矩形的所有姿态组成的状态。一般规律：对于 i+j=n , dp[n] 包含 dp[j] 拼接在 dp[i] 后组成的任何姿态。如：n=4 ，dp[4] 包含 dp[1] 拼接在 dp[

数学

贪心

脑筋急转弯

动态规划

871

・

2022.11.12

[Java] 递推找规律 & 图解分析

通过上面的归纳推导，可以发现有如下规律，假设n=i 最后一列为1个2x1的形状个数为 dp[i-1] 最后两列为2个1x2的形状个数为 dp[i-2], 以上两种情况是不存在镜像的。当最后j列来进行组合，前i-j用以前的结果进行拼接，我们发现当j>2时每次的种类数都为2，即镜像后形状不相同。因此这些可能为2 *

Java

动态规划

708

全部题解

多米诺和托米诺平铺

力扣官方题解

33316

2022.11.11

发布于未知归属地

官方题解

动态规划

C++

方法一：动态规划

考虑这么一种平铺的方式：在第 $i$ 列前面的正方形都被瓷砖覆盖，在第 $i$ 列后面的正方形都没有被瓷砖覆盖（ $i$ 从 $1$ 开始计数）。那么第 $i$ 列的正方形有四种被覆盖的情况：

一个正方形都没有被覆盖，记为状态 $0$ ；
只有上方的正方形被覆盖，记为状态 $1$ ；
只有下方的正方形被覆盖，记为状态 $2$ ；
上下两个正方形都被覆盖，记为状态 $3$ 。

使用 $dp [i] [s]$ 表示平铺到第 $i$ 列时，各个状态 $s$ 对应的平铺方法数量。考虑第 $i - 1$ 列和第 $i$ 列正方形，它们之间的状态转移如下图（红色条表示新铺的瓷砖）：

fig1

初始时 $dp [0] [0] = 0, dp [0] [1] = 0, dp [0] [2] = 0, dp [0] [3] = 1$ ，对应的状态转移方程（ $i > 0$ ）为：

dp [i] [0] dp [i] [1] dp [i] [2] dp [i] [3] = dp [i - 1] [3] = dp [i - 1] [0] + dp [i - 1] [2] = dp [i - 1] [0] + dp [i - 1] [1] = dp [i - 1] [0] + dp [i - 1] [1] + dp [i - 1] [2] + dp [i - 1] [3]

最后平铺到第 $n$ 列时，上下两个正方形都被覆盖的状态 $dp [n] [3]$ 对应的平铺方法数量就是总平铺方法数量。

Python3

C++

Java

JavaScript

Golang

class Solution:
    def numTilings(self, n: int) -> int:
        MOD = 10 ** 9 + 7
        dp = [[0] * 4 for _ in range(n + 1)]
        dp[0][3] = 1
        for i in range(1, n + 1):
            dp[i][0] = dp[i - 1][3]
            dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MOD
            dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % MOD
            dp[i][3] = (((dp[i - 1][0] + dp[i - 1][1]) % MOD + dp[i - 1][2]) % MOD + dp[i - 1][3]) % MOD
        return dp[n][3]

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 是总列数。
空间复杂度： $O (n)$ 。保存 $dp$ 数组需要 $O (n)$ 的空间。

方法二：矩阵快速幂

关于矩阵快速幂的讲解可以参考官方题解「70. 爬楼梯」的方法二，本文不再作详细说明。由方法一可知，平铺到某一列时的所有覆盖状态可以用一个列向量 $x$ 来表示，那么初始时 $x = [0001]^{T}$ 。一次状态转移等价于在左边乘上矩阵：

A = ⎣ ⎡ 0111001101011001 ⎦ ⎤

那么 $n$ 次状态转移后，所有覆盖状态对应的列向量为 $A^{n} x$ ，其中 $A^{n}$ 可以使用矩阵快速幂来计算。根据 $x$ 的值，可以知道最终所有的覆盖状态对应的列向量为 $A^{n}$ 的第 $3$ 列，返回该列向量的第 $3$ 个元素即可。

Python3

C++

Java

Golang

class Solution:
    def numTilings(self, n: int) -> int:
        MOD = 10 ** 9 + 7

        def multiply(a: List[List[int]], b: List[List[int]]) -> List[List[int]]:
            rows, columns, temp = len(a), len(b[0]), len(b)
            c = [[0] * columns for _ in range(rows)]
            for i in range(rows):
                for j in range(columns):
                    for k in range(temp):
                        c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD
            return c

        def matrixPow(mat: List[List[int]], n: int) -> List[List[int]]:
            ret = [
                [1, 0, 0, 0],
                [0, 1, 0, 0],
                [0, 0, 1, 0],
                [0, 0, 0, 1],
            ]
            while n:
                if n & 1:
                    ret = multiply(ret, mat)
                n >>= 1
                mat = multiply(mat, mat)
            return ret

        mat = [
            [0, 0, 0, 1],
            [1, 0, 1, 0],
            [1, 1, 0, 0],
            [1, 1, 1, 1],
        ]
        res = matrixPow(mat, n)
        return res[3][3]

复杂度分析

时间复杂度： $O (lo g n)$ ，其中 $n$ 是总列数。矩阵快速幂的时间复杂度为 $O (lo g n)$ 。
空间复杂度： $O (1)$ 。

下一篇题解

找不到规律？请看图！（Python/Java/C++/Go）

malog_

来自广东

2025.04.03

矩阵快速幂

class Solution {
public:
    int mod = 1e9+7;

    vector<vector<long long>> multiply(const vector<vector<long long>>& a, const vector<vector<long long>>& b) {
        int n = a.size();
        int m = b[0].size();
        int k = a[0].size();
        vector<vector<long long>> ans(n, vector<long long>(m));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                for (int c = 0; c < k; c++) {
                    ans[i][j] = (int)(((long long)a[i][c] * b[c][j] + ans[i][j]) % mod);
                }
            }
        }
        return ans;
    }

    vector<vector<long long>> power(vector<vector<long long>> m, int p) {
        int n = m.size();
        vector<vector<long long>> ans(n, vector<long long>(n));
        for (int i = 0; i < n; i++) {
            ans[i][i] = 1;
        }
        for (; p != 0; p >>= 1) {
            if ((p & 1) != 0) {
                ans = multiply(ans, m);
            }
            m = multiply(m, m);
        }
        return ans;
    }

    int f2(int n)
    {
        if(n == 0)
        {
            return 1;
        }
        if(n == 1)
        {
            return 2;
        }
        if(n == 2)
        {
            return 5;
        }

        vector<vector<long long>> start = { {5, 2, 1} };
        vector<vector<long long>> base = { {2, 1, 0} , {0, 0, 1} , {1, 0, 0} };
        vector<vector<long long>> ans = multiply(start, power(base, n - 2));
        return ans[0][0];
    }    

    int numTilings(int n) {
        return f2(n - 1);
    }
};

文件传输助手

来自江苏

2025.02.25

左下角有向上的拇指，为什么没有向下的呢？

老宋🐾

来自北京

2022.11.11

解这道题的第一步，是把题目翻译成人话。下面这一段，我表示不属于人话：

看了一下英文版，我表示英文版不但不属于人话，也不属于地球上任何一种鸟语：

不想做了，一读使人烦，二读使人躁，三读使人想摔电脑。

167

展示 18 条回复

ydnacyw

来自山东

2023.11.18

先点开评论，再点开题解

...

来自浙江

2022.11.12

展示 4 条回复

可爱抱抱呀😥

来自河北(编辑过)

2022.11.11

/*
@可爱抱抱呀
执行用时：2 ms, 在所有 Java 提交中击败了29.68%的用户
内存消耗：39.2 MB, 在所有 Java 提交中击败了7.74%的用户
2022年11月11日 17:33
*/
class Solution {
    int mod=(int)1e9+7,matrix[][]={{0,1,1,1},{0,0,1,1},{0,1,0,1},{1,0,0,1}}; 
    public int numTilings(int n) {
        long ans[][]=new long[n][4];
        ans[0]=new long[]{1,0,0,1};
        for(int i=1;i<n;i++){
            for(int j=0;j<4;j++){
                for(int k=0;k<4;k++){ans[i][j]+=ans[i-1][k]*matrix[k][j];}
                ans[i][j]%=mod;
            }
        }
        return (int)ans[n-1][3];
    }
}

滚动数组优化空间：

/*
@可爱抱抱呀
执行用时：2 ms, 在所有 Java 提交中击败了29.68%的用户
内存消耗：39.2 MB, 在所有 Java 提交中击败了5.16%的用户
2022年11月11日 17:39
*/
class Solution {
    int mod=(int)1e9+7,matrix[][]={{0,1,1,1},{0,0,1,1},{0,1,0,1},{1,0,0,1}}; 
    public int numTilings(int n) {
        long ans[]=new long[]{1,0,0,1};
        for(int i=1;i<n;i++){
            long arr[]=new long[4];
            for(int j=0;j<4;j++){
                for(int k=0;k<4;k++){arr[j]+=ans[k]*matrix[k][j];}
                arr[j]%=mod;
            }
            ans=arr;
        }
        return (int)ans[3];
    }
}

矩阵快速幂：

/*
@可爱抱抱呀
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：38.3 MB, 在所有 Java 提交中击败了78.71%的用户
2022年11月11日 19:34
*/
class Solution {
    long mod=(int)1e9+7,matrix[][]={{0,1,1,1},{0,0,1,1},{0,1,0,1},{1,0,0,1}}; 
    public int numTilings(int n) {
        long ans[]=new long[]{1,0,0,1};
        n--;
        while(n>0){            
            if(n%2==1){
                long arr[]=new long[4];
                for(int j=0;j<4;j++){
                    for(int k=0;k<4;k++){arr[j]+=ans[k]*matrix[k][j];}
                    arr[j]%=mod;
                }
                ans=arr;
            }            
            matrix=square();
            n>>=1;
        }
        return (int)ans[3];
    }
    long[][] square(){
        long ans[][]=new long[4][4];
        for(int i=0;i<4;i++){
            for(int j=0;j<4;j++){
                for(int k=0;k<4;k++){ans[i][j]+=matrix[i][k]*matrix[k][j];}
                ans[i][j]%=mod;
            }
        }
        return ans;
    }
}

当然数据量不大，可以直接打表：

/*
@可爱抱抱呀
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：38.6 MB, 在所有 Java 提交中击败了54.19%的用户
2022年11月11日 19:51
*/
class Solution {
    int ans[]={1,2,5,11,24,53,117,258,569,1255,2768,6105,13465,29698,65501,144467,318632,702765,1549997,3418626,7540017,16630031,36678688,80897393,178424817,393528322,867954037,914332884,222194076,312342182,539017241,300228551,912799284,364615795,29460134,971719552,308054885,645569904,262859346,833773577,313117044,889093434,611960431,537037899,963169225,538298867,613635626,190440463,919179793,451995198,94430852,108041490,668078178,430587201,969215892,606509948,643607090,256430058,119370057,882347204,21124452,161618961,205585119,432294690,26208334,258001787,948298264,922804855,103611483,155521223,233847294,571306071,298133358,830114010,231534077,761201512,352517020,936568117,634337732,621192477,178953057,992243846,605680155,390313360,772870559,151421259,693155878,159182301,469785861,632727593,424637480,319060814,270849214,966335908,251732616,774314446,514964786,281662181,337638801,190242381,662146943,661932680,514107734,690362404,42657474,599422682,889207761,821072989,241568646,372345046,565763074,373094787,118534613,802832300,978759380,76053359,954939018,888637402,853328156,661595316,211828020,276984189,215563687,642955394,562894970,341353620,325662627,214220217,769794054,865250728,944721666,659237372,183725458,312172575,283582515,750890488,813953544,911489596,573869666,961692869,834875320,243620292,448933446,732742205,709104695,867142829,467027849,643160386,153463587,773955023,191070418,535604423,845163862,881398135,298400679,441965213,765328554,829057780,100080759,965490072,760037910,620156572,205803202,171644307,963445186,132693560,437031427,837508033,807709619,52450651,942409335,692528275,437507194,817423716,327375693,92258573,1940855,331257403,754773379,511487606,354232608,463238588,437964775,230162151,923562890,285090541,800343233,524249342,333589218,467521662,459292659,252174529,971870720,403034085,58242692,88356097,579746279,217735243,523826583,627399438,472534112,468894800,565189031,602912167,674719127,914627278,432166709,539052538,992732347,417631389,374315309,741362958,900357298,175029891,91422733,83202757,341435405,774293543,631789836,605015070,984323676,600437174,805889411,596102484,792642135,391173667,378449811,549541750,490257160,35***124,267469991,25197135,409358394,86186772,197570679,804499752,695186269,587943210,980386165,655958585,899860373,780106897,216172365,332205096,444517082,105206522,542618140,529753355,164713225,872044590,273842521,712398267,296841110,867524741,447447735,191736573,250997880,949443495,90623549,432244978,813933444,718490430,869225831,552385092,823260607,515747031,583879147,991018894,497784805,579448750,149916380,797617565,174683866,499284112,796185782,767055423,33394944,862975670,493006749,19408435,901792540,296591815,612592065,126976656,550545127,713682312,554341273,659227666,32137630,618616533,***60725,825059073,268734665,433930048,692919162,654572982,743076005,179071158,12715291,768506587,716084325,444883934,658274448,32633207,510150348,678575137,389783474,289717289,258009708,905802890,101323055,460655818,827114519,755552086,971759983,770634471,296821014,565402004,901438472,99697944,764797892,431034242,961766428,688330734,807695703,577157820,842646367,492988423,563134659,968915678,430819765,424774182,818464035,67747821,560269824,939003676,945755166,451780142,842563953,630883058,713546251,269656441,170195933,53938110,377532661,925261255,904460613,186453873,298168994,500798594,188051054,674271102,849340791,886732629,447736346,744813476,376359567,200455473,145724415,667808397,536072260,217868928,103546246,743164752,704198425,511943089,767050923,238300257,988543603,744138115,726576480,441696549,627531206,981638885,404974305,437479809,856598496,118171283,673822375,204243232,526657747,727137862,658518949,843695638,414529124,487577190,818850011,52229132,592035454,2920905,58070942,708177338,419275574,896622090,501421504,422118575,740859233,983139963,388398487,517656200,18452349,425303185,368262563,754977475,935258128,238778805,232535078,400328277,39435352,311405782,23139834,85715020,482835822,988811478,63337962,609511746,207834956,479007874,567527487,342889923,164787713,897102913,137095735,438979183,775061272,687218272,813415720,401892698,491003661,795423035,992738761,476481169,748385366,489509479,455500120,659385599,808280670,72061446,803508491,415297638,902656722,608821921,632941473,168539654,945901229,524743917,218027481,381956184,288656278,795340037,972636251,233928766,263197562,499031368,231991495,727180552,953392465,138776411,4733367,962859199,64494795,133722957,230305106,525105007,183932964,598171034,721447068,626827093,851825213,425097480,477022046,805869298,36836062,550694170,907257631,851351317,253396790,414051204,679453718,612304219,638659635,956772981,525850167,690359962,337492891,200835942,92031839,521556569,243949073,579929985,681416532,606782130,793494238,268404994,143592111,80678453,429761900,3115904,86910261,603582422,210280741,507471743,618525901,447332536,402136808,422799510,292931549,987999906,398799308,90530158,169060215,736919738,564369627,297799462,332518655,229406930,756613322,845745292,920897507,598408322,42561922,6021344,610451010,263463935,532949214,676349431,616162790,765274787,206898991,29960765,825196317,857291618,744543994,314284291,485860193,716264373,746813030,979486246,675236851,97286718,174059675,23356194,143999106,462057887,947471968,38943028,539943943,27359840,93662708,727269359,481898551,57459803,842188965,166276467,390012737,622214432,410705324,211423378,45061181,500827686,213078743,471218667,443265013,99608762,670436191,784137388,667883531,6203239,796543866,260971249,528145737,852835333,966641908,461429539,775694404,518030702,497490936,770676269,59383226,616257388,3191031,65765288,747787964,498766952,63299185,874386334,247539606,558378397,991143121,229825834,18030058,27203230,284232294,586494646,200192515,684617324,955729287,111651075,907919474,771568221,654787510,217494480,206557174,67901851,353298182,913153538,894208920,141716008,196585547,287380007,716476022,629537584,546455168,809386351,248310272,43075705,895537761,39385780,121847265,139232284,317850348,757547961,654328199,626506739,10561425,675451049,977408830,965379078,606209191,189827198,345033467,296276118,782379434,909792328,115860760,14100947,937994222,991849197,997799334,933592876,859034935,715869190,365331242,589697412,895264007,155859242,901415896,698095785,552050805,5517492,709130769,970312336,946142157,601415069,173142460,292427070,186269202,545680864,383788791,953846784,453374418,290537620,534922017,523218445,336974503,208871016,940960477,218895443,646661902,234284267,687463977,21589842,277463951,242391872,506373586,290211116,822814104,152001780,594214676,11243442,174488664,943192004,897627443,969743543,882679076,662985581,295714691,474108451,611202476,518119636,510347716,631897901,781915431,74178564,780255029,342425475,759029514,298314043,939053561,637136622,572587280,84228107,805592836,183772938,451773983,709140795,602054521,655883018,20906817,643868155,943619321,908145452,460159045,863937404,636020246,732199530,328336450,292693139,317585801,963508052,219709229,757004259,477516556,174742334,106488920,690494396,555731119,217951151,126396691,808524501,835000146,796396976,401318439,637637017,71670996,544660431,726957872,525586733,595833890,918625645,362838009,321509901,561645440,486128882,293767658,149180749,784490380,862748411,874677564,533845494,930439392,735556334,4958148,940355688,616267696,237493533,415342747,446953183,131399892,678142531,803238238,737876361,153895239,111028709,959933779,73762783,258554275,477042322,27847420,314249115,105540545,238928510,792106135,689752808,618434119,28974359,747701526,113837157,256648673,260998865,635834887,528318440,317635738,271106356,70531145,458698028,188502405,447535955,353769931,896042267,239620475,833010881,562064015,363748498,560507870,683079748,729907987,20323830,723727408,177362789,375049408,473826217,125015216,625079840,723985890,572986989,771053811,266093498,105173978,981401767,228897018,562968014,107337781,443572580,450113167,7564108,458700796,367514752,742593612,943888013,255290764,253175133,450238272,155767301,564709735,579657735,315082764,194875256,969408247,253899244,702673744,374755721,3410679,709495102,793745918,590902508,891300111,576346126,743594753,378489603,333325325,410245396,198980388,731286101,872817591,944615563,620517213,113852003,172319562,965156337,44164663,260648888,486454106,17072868,294794624,76043347,169159562,633113748,342270836,853701234,340516202,23303233,900307700,141131588,305566409,511440511,164012603,633591615,778623734,721260064,76111729,930847192,582954434,242020590,414888365,412731157,67482897,549854159,512439468,92361826,734577811,981595083,55551978,845681767,672958603,401469177,648620114,970198824,341866811,332353729,634906275,611679354,555712430,746331128,104341596,764395622,275122358,654586312,73568232,422258822,499103949,71776123,565811068,630726078,333228272,232267605,95261281,523750834,279769266,654799813,833350453,946470165,547740129,928830704,804131559,156003233,240837163,285805878,727614989,696067134,677940139,83495253,863057640,404055405,891606063,646269752,696594902,284795853,215861451,128317797,541431447,298724338,725766473,992964386,284653096,295072658,583109695,450872479,196817609,976744913,404362291,5542184,987829281,380020839,765583862,518996991,418014814,601613483,722223950,862462707,326538883,375301709,613066118,552671112,480643926,574353963,701379031,883401981,341157911,383694846,650791666,642741236,669177311,989146281,621033784,911244872,811636011,244305792,399856449,611348902,467003589,333863620,279076135,25155852,384175324,47426776,120009404,624194132,295815033,711639470,47473058,390761149,493161761,33796573,458354295,409870344,853537261,165428803,740727950,334993147,835415097,411558130,158109400,151633890,714825910,587761213,327156309,369138521,326038248,979232805};
    public int numTilings(int n) {
        return ans[n-1];
    }
}