想借著這一個(gè)題回顧一下動(dòng)態(tài)規(guī)劃問題的基本解法，讓解題方法清晰有條理，希望更多的人可以更輕松的理解動(dòng)態(tài)規(guī)劃！

目錄

【題目】

【本題解題思路】

【DP模版】

總體方針：

具體解題時(shí)的套路：

---

?【題目】

?

??【本題解題思路】

———類似題目：覆蓋墻壁 - 洛谷（很多經(jīng)典題解在里面）

1、確定子狀態(tài)：

我最終要求解的是：用兩種類型的積木將2 x n的畫卷填滿時(shí)有著多少種組合方案。（圍繞最終要求解的問題確定子問題）

所以子問題應(yīng)該是在長(zhǎng)度為n的情況下有多少種解法。

所以用一維數(shù)組dp[i] 存儲(chǔ)長(zhǎng)度為i 時(shí)的方案數(shù)。

2、確定轉(zhuǎn)移的邊界情況和初始狀態(tài)：

這里先正著推，已知n=3時(shí)dp[3]=5，那么就可以先明確n=1,n=2時(shí)對(duì)應(yīng)的dp[i],即dp[1]=1,dp[2]=2;

然后發(fā)現(xiàn)沒有什么明顯的規(guī)律呢，那就再倒著來

3、確定狀態(tài)轉(zhuǎn)移方式：

為了方便表述，設(shè)畫卷長(zhǎng)度為len；

我想知道畫卷長(zhǎng)度為len=n時(shí)的值，那么我就找他的上一層 len=n-1時(shí)的狀態(tài)，看看有沒有什么關(guān)聯(lián)。為了形成填滿畫卷的狀態(tài)，我的最后一塊位置可以怎么擺放積木呢，從積木的兩種類型出發(fā)，發(fā)現(xiàn)他可以形成四種狀態(tài)。這里用分類的思想將所有的選擇羅列出來，找規(guī)律。

如圖所示，最后一次有如下選擇：

（1）最后一次選豎著的I ，那么dp[n]=dp[n-1]。

因?yàn)樽詈笠晃还潭ê昧司瓦@一種選擇，即1*dp[n-1]。如圖1；

（2）最后一次選橫著的I ,那么為了填補(bǔ)上畫卷，第二行也只能選橫著的I 這兩個(gè)橫著的I作為一個(gè)整體是一種填補(bǔ)畫卷的方式。此時(shí)dp[n]=dp[n-2];

如圖2所示。

前兩種狀態(tài)都很明顯，但是如果選用L形的怎么羅列呢：

（3）L型垂直翻轉(zhuǎn)前后算兩種狀態(tài)，如圖3、4.? 下面僅根據(jù)其中的一種情況來討論，最后因?yàn)榉D(zhuǎn)所有的結(jié)果×2 即可。

A.可以用兩個(gè)L形成長(zhǎng)度為3的整體來填補(bǔ)畫卷，dp[n]=dp[n-3]，如圖5;

B.采用兩個(gè)L和一個(gè)橫著的I的方式形成一個(gè)整體作為一種方法填補(bǔ)，dp[n]=dp[n-4]，如圖6;

C.同上，還可以采用在兩側(cè)兩個(gè)L中間包裹多個(gè)橫著的I的方式來填補(bǔ)，每多一個(gè)橫著的I相當(dāng)于這個(gè)用于填補(bǔ)的圖像整體的長(zhǎng)度+1。所以類推得到dp[n]=dp[n-5]，dp[n-6]，...? 如圖7；

綜上所述，形成填滿畫卷的前一個(gè)整體的狀態(tài)可以采用如上這些方式，所以他的方案總數(shù)就有:

dp[n]=dp[n-1]+dp[n-2]+2*（dp[n-3]+dp[n-4]+...dp[0]）;

假如用前綴和sum[n]表示前n個(gè)長(zhǎng)度的方案總和，dp[n]=sum[n-1]+sum[n-3];

但是我這里只求了n=1---3的情況，n=4時(shí)情況雖然有點(diǎn)復(fù)雜，但是也還是不好求（哈哈）。

所以有沒有什么化簡(jiǎn)的方式呢，大家記不記得高考時(shí)第一個(gè)大題考的數(shù)組的性質(zhì)，這里就可以用來變換公式；

dp[n]=sum[n-1]+sum[n-3];

dp[n-1]=sum[n-2]+sum[n-4];

上下相減發(fā)現(xiàn)? dp[n]-dp[n-1]=dp[n-1]+dp[n-3];

所以，dp[n]=2*dp[n-1]+dp[n-3]???

這就把遞推公式推出來了，完美撒花！

【DP模版】

總體方針：

凡是動(dòng)態(tài)規(guī)劃問題，可以從以下三個(gè)角度考慮，確定求解問題的基本思路：

（有時(shí)是二維問題或者多維問題時(shí)可以考慮用二維或者多維數(shù)組）

動(dòng)態(tài)規(guī)劃問題具有兩個(gè)性質(zhì)：

（1）無后效性：每個(gè)子問題的解都是基于之前子問題的解，而不受后續(xù)子問題解的影響。這意味著我們可以獨(dú)立地解決每個(gè)子問題，然后將這些解組合起來形成一個(gè)最優(yōu)解。即當(dāng)前狀態(tài)的解只受此狀態(tài)之前（就是過去的狀態(tài)）的影響，一經(jīng)確定，未來的狀態(tài)不影響當(dāng)前狀態(tài)的結(jié)果。

（換成人話就是，當(dāng)前狀態(tài)的結(jié)果是由之前狀態(tài)形成的，一旦確定，后續(xù)的狀態(tài)對(duì)他沒有影響）

（2）子問題重疊性：每個(gè)子問題之間類似于嵌套的關(guān)系，我想求這個(gè)子問題，就必須先解決比他規(guī)模更小的、具有同樣規(guī)律的子問題。

具體解題時(shí)的套路：

1、按照題目的求解問題，確定子問題是什么，把存儲(chǔ)每個(gè)子問題的數(shù)據(jù)結(jié)構(gòu)定義出來；

2、根據(jù)題目中給的信息，自己推理、枚舉出來所有的可以獲得的關(guān)于解的信息，看看是否存在什么規(guī)律。這里推倒的方式往往是從邊界開始往前推導(dǎo)，觀察前后狀態(tài)之間的聯(lián)系?；蛘呤菑某跏紶顟B(tài)向后推導(dǎo)，找規(guī)律。

?