今天我們先來講一下狀態(tài)壓縮dp(也稱狀壓dp)。狀壓dp,顧名思義,就是把狀態(tài)壓縮起來。比如對于8*8 的棋盤,每個位置可以放一個棋子,對于在第i行第2個位置和第6個位置放了棋子,我們可能需要8維或9維數(shù)組表示。因此我們就有了把一行狀態(tài)壓縮成一個數(shù)字的做法。一般我們會轉化為二進制,如果每個位置可以有3種狀態(tài),那我們可以采用三進制。這樣只需要一個大小為2^8的一維數(shù)組我們就可以存下所有狀態(tài),這就是狀態(tài)壓縮。
成都創(chuàng)新互聯(lián)是一家專業(yè)提供寬甸企業(yè)網(wǎng)站建設,專注與成都網(wǎng)站制作、成都網(wǎng)站建設、外貿營銷網(wǎng)站建設、H5開發(fā)、小程序制作等業(yè)務。10年已為寬甸眾多企業(yè)、政府機構等服務。創(chuàng)新互聯(lián)專業(yè)網(wǎng)站建設公司優(yōu)惠進行中。
eg1 ? 現(xiàn)在有 n*m 的方格棋盤,和無限的 1*2 的骨牌,問有多少種方法能用骨牌 鋪滿棋盤。 ? 1<=n,m<=11. 算法分析: 首先 n*m 是奇數(shù)一定拼不出來。使用狀態(tài)壓縮,如果第 i 個位置上放骨牌,就在二進制對應位置填 1,否則是 0. 用 f[i][s] 表示填到了第 i 行狀態(tài)是 s 的方案數(shù)。答案就是 f[n][(1<m) { return ; } if(i==m) { ++tot; from[tot]=pre; to[tot]=now; return ; } dfs(i+2,now<<2|3,pre<<2|3); dfs(i+1,now<<1,(pre<<1)|1); dfs(i+1,now<<1|1,pre<<1); } 主函數(shù): int f[12][1<<11]; dfs(0,0,0); f[0][(1<
網(wǎng)站欄目:編程兔暑假3.5階段集訓Day6——狀壓(狀態(tài)壓縮)dp、dp優(yōu)化以及圖論
路徑分享:http://weahome.cn/article/dsoigjd.html