超詳細(xì)傻瓜級教學(xué)，包看包會。

創(chuàng)新互聯(lián)主營靖州網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司,主營網(wǎng)站建設(shè)方案,重慶APP軟件開發(fā),靖州h5微信小程序定制開發(fā)搭建,靖州網(wǎng)站營銷推廣歡迎靖州等地區(qū)企業(yè)咨詢

關(guān)鍵思想：將2*1的畫布看成初始畫布，后面不斷加1列空白列構(gòu)成其他畫布。所以最后一個畫布的積木構(gòu)成可以由之前的畫布積木構(gòu)成來推導(dǎo)。

下面為初始畫布（僅有放一個i型積木的可能）

我們將畫布上最后兩格都空的情況稱為情況0

只空上格稱為情況1

只空下格稱為情況2

不空稱為情況3（即滿足題目條件的情況）

所以定義一個二維數(shù)組dp[n+1][4]（動態(tài)規(guī)劃算法簡稱DP，這個數(shù)組名就這樣來的）

用來存儲n長度畫布的4種情況的可能的構(gòu)成次數(shù)（即情況0123 為索引，所存的數(shù)為可能出現(xiàn)的構(gòu)成的次數(shù)）

int[][] dp=new int[n+1][4];
        dp[1][0]=1;
        dp[1][3]=1;//情況初始化，初始畫布下僅在情況3和情況0

一格畫布只能出現(xiàn)情況3或0，12無法出現(xiàn)，所以將n=1時進(jìn)行賦值。

再多一格時有這幾種情況

即012的情況各有一種可能，3有兩種可能

再往后添加一格空白，則012各有兩種可能，3有五種可能

我們可以發(fā)現(xiàn)規(guī)律：

0情況就是上一個畫布下3情況的可能（畢竟多加一列畫布，前面是滿的，后面多一列空白就滿足了0情況）

1情況是上一個畫布下0情況家+2情況的和?（即上一個畫布的0情況加一個L型可滿足，或上一個畫布的2情況加一個橫I型亦可滿足）

情況2與情況1基本一樣不再贅述

情況3（=上一個畫布的情況0+情況1+情況2+情況3（如下圖））

注意情況0的I型只能橫放，否則與情況3重復(fù)。

則有如下代碼

for(int i=2;i<=n;i++){
            //情況0的計算
            dp[i][0]=dp[i-1][3];
            //情況1和2的計算
            dp[i][1]=(dp[i-1][0]+dp[i-1][2])%mod;
            dp[i][2]=(dp[i-1][0]+dp[i-1][1])%mod;
            //情況3的計算
            dp[i][3]=(((dp[i-1][0]+dp[i-1][1])%mod+dp[i-1][2])%mod+dp[i-1][3])%mod;
        }
        System.out.print(dp[n][3]);

情況3的計算之所以要取模多次是為了保證不爆容器，畢竟一個數(shù)不論取多少次模都等于取一次模，所以無需在意多次取模對數(shù)據(jù)造成的影響。

最后輸出dp[n][3]即為答案。完整代碼如下

import java.util.Scanner;
// 1:無需package
// 2: 類名必須Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此輸入您的代碼...
         int mod=1000000007;
        int n=scan.nextInt();
        int[][] dp=new int[n+1][4];
        dp[1][0]=1;
        dp[1][3]=1;//情況初始化，初始畫布下僅在情況3
        for(int i=2;i<=n;i++){
            //情況0的計算
            dp[i][0]=dp[i-1][3];
            //情況1和2的計算
            dp[i][1]=(dp[i-1][0]+dp[i-1][2])%mod;
            dp[i][2]=(dp[i-1][0]+dp[i-1][1])%mod;
            //情況3的計算
            dp[i][3]=(((dp[i-1][0]+dp[i-1][1])%mod+dp[i-1][2])%mod+dp[i-1][3])%mod;
        }
        System.out.print(dp[n][3]);
        scan.close();
    }
}

完！

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

當(dāng)前文章：動態(tài)規(guī)劃問題（2022藍(lán)橋杯積木畫題目）-創(chuàng)新互聯(lián)
當(dāng)前網(wǎng)址：http://weahome.cn/article/cohiej.html