【線上程式設計産品介紹】
阿裡雲開發者社群線上程式設計：
免費刷題大神器，助你拿到好offer
周賽月賽不停歇，做題還能領獎品
大賽筆試全真題，常做常新有驚喜
點選連結開始産品體驗：
https://developer.aliyun.com/coding 本文為大家介紹的是“120.木棒拼接”的解法探究。先來看一下題目内容：題目詳情
等級：困難
知識點：二進制枚舉、DP
檢視題目：木棒拼接Codancer現在由n根木棒，第i根木棒的長度為l[i]，并且每根木棒隻有紅、黃、藍三種顔色。
現在codancer想得到一根長度為L的木棍，codancer可以選擇其中的一些按照一定的順序把這若幹根木棒拼接起來，但是codancer要求相鄰的兩根木棒的顔色不得相同并且木棒的長度總和必須是L。
現在codancer想知道有多少種拼接方案（隻要是存在順序不同或者木棒不同就不是一同種方案）。
由于答案比較大，是以你隻需要輸出答案對1000000000+7取餘的結果即可。
輸入n和T，代表木棒的總數和所需要構造的木棍的長度T。
接下來n行，每行兩個數組l[i]和c[i]，代表第i根木棒的長度和顔色。(1<=n<=15,1<=L<=225,1<=l[i]<=15,1<=c[i]<=3)
輸出方案數對10^9+7取餘的結果。
示例1
輸入：
3
[[1,1],[1,2],[1,3]]
輸出：
6
注意
所有的排列方案為:
[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]
解題思路：動态規劃
根據樣例所有的排列方案為:
考慮使用動态規劃算法，令dpi表示在第i中狀态中最後一根木棒是第j根木棒的方案數：
那麼可以得到轉移方程為:
dp[i|(1<<k)][c[k]]=(dp[i|(1<<k)][c[k]]%mod+dp[i][2]%mod+dp[i][3]%mod)%mod;(c[k]==1)
dp[i|(1<<k)][c[k]]=(dp[i|(1<<k)][c[k]]%mod+dp[i][1]%mod+dp[i][3]%mod)%mod;(c[k]==2)
dp[i|(1<<k)][c[k]]=(dp[i|(1<<k)][c[k]]%mod+dp[i][1]%mod+dp[i][2]%mod)%mod;(c[k]==3)
最後枚舉所有的可行性狀态計數即可，最終時間複雜度為n*(2^n)
看完之後是不是有了答題思路了呢，快來練練手吧：
120.木棒拼接線上程式設計周賽、月賽火熱進行中，更有限時答題活動，定制衛衣、雙肩背包、機械鍵盤等多重好禮等你來拿~每天都有好禮相送~點選了解周賽詳情：
線上程式設計3月份比賽正式開啟！機械鍵盤等你拿！