【在线编程产品介绍】
阿里云开发者社区在线编程：
免费刷题大神器，助你拿到好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
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]
解题思路：动态规划
根据样例所有的排列方案为:
[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月份比赛正式开启！机械键盘等你拿！
