動(dòng)態(tài)規(guī)劃算法的過(guò)程是隨著階段的增長(zhǎng)，在每個(gè)狀態(tài)維度上的分界點(diǎn)組成了DP拓展的輪廓。對(duì)于某些問(wèn)題，我們需要在動(dòng)態(tài)規(guī)劃的狀態(tài)中記錄一個(gè)集合，保存這個(gè)輪廓的詳細(xì)信息，以便于進(jìn)行狀態(tài)轉(zhuǎn)移。若集合大小不超過(guò)N，集合中每個(gè)元素都是小于k的自然數(shù)，則我們可以把這個(gè)集合看做一個(gè)N位k進(jìn)制數(shù)，以一個(gè)[0,k^N-1]之間的十進(jìn)制整數(shù)的形式作為DP狀態(tài)的一維。這種把集合轉(zhuǎn)化為整數(shù)記錄在DP狀態(tài)中的一類算法被稱之為狀態(tài)壓縮動(dòng)態(tài)規(guī)劃算法。
我們先用一個(gè)例子來(lái)說(shuō)明狀態(tài)壓縮DP的一般解法：
例一：小國(guó)王
在n×n 的棋盤上放 k 個(gè)國(guó)王，國(guó)王可攻擊相鄰的 8 個(gè)格子，求使它們無(wú)法互相攻擊的方案總數(shù)。
輸入格式
共一行，包含兩個(gè)整數(shù) n 和 k。
輸出格式
共一行，表示方案總數(shù)，若不能夠放置則輸出0。
數(shù)據(jù)范圍
1≤n≤10,
0≤k≤n^2
輸入樣例：
3 2
輸出樣例：
16
國(guó)王攻擊范圍示意圖
紅色表示國(guó)王位置，藍(lán)色表示攻擊范圍
算法分析：
類似于棋盤放置類問(wèn)題， 在一般情況下我們會(huì)采用暴搜（如八皇后問(wèn)題）,但如果我們直接暴搜，時(shí)間復(fù)雜度為O（）,明擺著會(huì)超時(shí)的，因此可以考慮用記憶化搜索來(lái)優(yōu)化。
于是我們用動(dòng)態(tài)規(guī)劃來(lái)考慮這個(gè)問(wèn)題：
動(dòng)態(tài)規(guī)劃的轉(zhuǎn)移方程，一般由最后一個(gè)不同點(diǎn)來(lái)定，由國(guó)王攻擊方式我們可以發(fā)現(xiàn)，
第i層放置國(guó)王的行為受到第 i - 1 層和第 i + 1 層以及第 i 層國(guó)王影響。
那么我們可以按照一般套路，從上往下枚舉每一行，這樣考慮第 i 層狀態(tài)時(shí)，只需考慮 i?1 層的狀態(tài)即可。
于是，我們可以考慮把層數(shù) i 作為動(dòng)態(tài)規(guī)劃的 一個(gè)階段進(jìn)行線性DP；
根據(jù)一般的DP思考方式，我們記錄第 i 階段所需要的信息；
第 i 階段需要記錄的就是前 i 層放置的國(guó)王數(shù)量 j，以及在第 i 層的 棋盤狀態(tài) s。
這里，我們先分析一下，哪些棋盤狀態(tài)是合法的， 以及哪些棋盤轉(zhuǎn)移的狀態(tài)是合法的（注意這兩個(gè)狀態(tài)，后面代碼實(shí)現(xiàn)時(shí)會(huì)用到）
合法的棋盤狀態(tài)：
如上圖所示，藍(lán)色方塊為擺放國(guó)王的位置，紅色方塊為國(guó)王的攻擊范圍；
只要任意王之間只要不相鄰，那么就是合法的狀態(tài)；
棋盤轉(zhuǎn)移的合法狀態(tài)：
如上圖所示：
只要任意國(guó)王的縱坐標(biāo)不相鄰，就是合法的轉(zhuǎn)移狀態(tài)。
那么怎么用代碼實(shí)現(xiàn)表示這些狀態(tài)呢？
我們可以用二進(jìn)制來(lái)表示這些狀態(tài)
我們給它標(biāo)上號(hào)，讓有國(guó)王的位置設(shè)為1，沒(méi)國(guó)王的位置設(shè)為0，于是可以得到(0100010)；于是，我們可以用(state >> i ) == 1, 來(lái)判斷在當(dāng)前狀態(tài)s下的第i個(gè)位置(0 <= i < n)是否放了國(guó)王。同時(shí)，因?yàn)槊杜ei-1層的狀態(tài)和第i層的狀態(tài)所需的循環(huán)過(guò)多導(dǎo)致時(shí)間復(fù)雜度很高，所以在這里我們運(yùn)用預(yù)處理的方式來(lái)解決此題。
狀態(tài)表示：f[ i ][ j ][ s ]所有只擺了前i行，已經(jīng)擺了j個(gè)國(guó)王并且第i行擺放狀態(tài)是s的所有方案集合
狀態(tài)轉(zhuǎn)移方程：f[ i ][ j ][ state[a] ] += f[ i - 1 ][ j - c ][ state[b] ] (c是在選擇狀態(tài)a時(shí)，放置的國(guó)王數(shù)量)
狀態(tài)分析圖：(我們把第i行國(guó)王的放置方式，作為集合)
代碼如下：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
const int N = 12, M = 1 << 10, K = 110;
int n, m;
vector<int> state;
int cnt[M]; //狀態(tài)state[a]的國(guó)王個(gè)數(shù)
vector<int> head[M];//head[i] 里存儲(chǔ)在第i行狀態(tài)為state[a]的情況下，上一行狀態(tài)可以取到的合法狀態(tài)statep[b]
LL f[N][K][M]; //狀態(tài)轉(zhuǎn)移方程，存方案數(shù)
bool check(int state)
{
for(int i = 0;i < n;i ++) //同一行兩個(gè)國(guó)王不能相鄰
if((state >> i & 1) && (state >> i + 1 & 1))
return false;
return true;
}
int count(int state) //統(tǒng)計(jì)該狀態(tài)下國(guó)王，即1的個(gè)數(shù)
{
int res = 0;
for(int i = 0;i < n;i ++) res += state >> i & 1;
return res;
}
int main()
{
cin >>n >> m;
//預(yù)處理所有合法狀態(tài) (對(duì)于這兩個(gè)狀態(tài)壓縮有疑惑的，看看上面的圖)
for(int i = 0;i < 1 << n;i ++)
if(check(i))
{
state.push_back(i); //將合法方案存入state
cnt[i] = count(i);
}
//預(yù)處理所有合法狀態(tài)的合法轉(zhuǎn)移
for(int i = 0;i < state.size();i ++)
for(int j = 0;j < state.size();j ++)
{
int a = state[i], b = state[j];
if((a & b) == 0 && check(a | b)) //a & b 指第i行和i-1行不能在同列有國(guó)王， check(a|b) == 1 指i和i -1行不能相互攻擊到
head[i].push_back(j); //head[i] 里存儲(chǔ)在第i行狀態(tài)為state[a]的情況下，上一行狀態(tài)可以取到的合法狀態(tài)statep[b]
}
f[0][0][0] = 1; //求方案數(shù)時(shí)，初始方案需要為1,因?yàn)槿靠?nbsp;也是一種方案
for(int i = 1;i <= n + 1;i ++) //枚舉每一行
for(int j = 0;j <= m;j ++) //國(guó)王數(shù)量
for(int a = 0;a < state.size();a ++) //枚舉合法方案
for(int b : head[a])
{
int c = cnt[state[a]]; //狀態(tài)state[a]的國(guó)王個(gè)數(shù)
if(j >= c)
f[i][j][state[a]] += f[i - 1][j - c][state[b]]; //f[i][state[a]], 在第i行狀態(tài)為i時(shí)，所有i - 1行的狀態(tài)數(shù)量
//因?yàn)閟tate[a]和a呈映射關(guān)系，所也可以寫成
// f[i][j][a] += f[i - 1][j - c][b];
}
cout << f[n + 1][m][0] << endl;//我們假設(shè)擺到n + 1行，并且另這一行狀態(tài)為0,那么即得到我們想要的答案，
//如果我們用f[n][m][]來(lái)獲取答案，那么我們就要枚舉最后一行的所有狀態(tài)取最大值，來(lái)得到答案。Java代碼：
import java.util.*;
public class Main{
static int N = 12,M = 1 << 10,K = 110;
static int n,m;
//當(dāng)前走到了第i行,并且已經(jīng)放了j個(gè)國(guó)王,且當(dāng)前第i行的狀態(tài)是s的方案的集合
static long[][][] f = new long[N][K][M];
static List<Integer> state = new ArrayList<>();//存所有合法狀態(tài)
static ArrayList<Integer>[] head = new ArrayList[M];//存合法狀態(tài)所有能夠走到的其他狀態(tài)
static int[] cnt = new int[M];//存每個(gè)合法狀態(tài)對(duì)應(yīng)有多少個(gè)1
//判斷是不是沒(méi)有兩個(gè)相鄰的1
public static boolean check(int state){
for (int i = 0 ; i < n ; i ++ )
if ((state >> i & 1) == 1 && (state >> i + 1 & 1 ) == 1)
return false;
return true;
}
//統(tǒng)計(jì)這個(gè)state有多少位是1
public static int count(int state){
int res = 0;
for(int i = 0 ; i < n ; i ++ ){
if ((state >> i & 1) == 1){
res ++;
}
}
return res;
}
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
//首先將所有合法狀態(tài)找出來(lái)
for (int i = 0 ; i < 1 << n ; i ++ ){
if (check(i)){ //如果合法
state.add(i);//將他存下來(lái)
cnt[i] = count(i);//然后計(jì)算一下這個(gè)狀態(tài)有多少個(gè)1
}
}
//接下來(lái)是尋找合法狀態(tài)所有能夠走到的其他狀態(tài)
for (int i = 0 ; i < state.size(); i ++ ){
for (int j = 0 ; j < state.size(); j ++ ){
int a = state.get(i);
int b = state.get(j);
if ((a & b) == 0 && check(a | b)){
//如果這個(gè)數(shù)a還沒(méi)有存過(guò)數(shù)，那就新建一個(gè)a鏈表放
if(head[i] == null){
head[i] = new ArrayList<>();
}
//創(chuàng)建完之后才能放
head[i].add(j);
}
}
}
//初始化
f[0][0][0] = 1;
for (int i = 1 ; i <= n + 1; i ++ ){
for (int j = 0 ; j <= m ; j ++ ){
for (int a = 0; a < state.size(); a ++ ){
for (int b : head[a]){
int c = cnt[state.get(a)];
if(j >= c){
f[i][j][a] += f[i - 1][j - c][b];
}
}
}
}
}
System.out.println(f[n + 1][m][0]);
}
}優(yōu)化：
通常，在內(nèi)存限制較緊時(shí)，我們可以利用滾動(dòng)數(shù)組來(lái)優(yōu)化
由于第 i 階段狀態(tài)只會(huì)用到第 i?1 階段的狀態(tài)，因此我們可以采用滾動(dòng)數(shù)組來(lái)優(yōu)化空間
也就是在枚舉行時(shí)，將數(shù)組下標(biāo)&1, 這樣得到的值都是0 或 1 ，以此進(jìn)行空間的優(yōu)化
//滾動(dòng)數(shù)組優(yōu)化
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
const int N = 12, M = 1 << 10, K = 110;
int n, m;
vector<int> state;
int cnt[M];
vector<int> head[M];
LL f[2][K][M];
bool check(int state)
{
for(int i = 0;i < n;i ++) //同一行兩個(gè)國(guó)王不能相鄰
if((state >> i & 1) && (state >> i + 1 & 1))
return false;
return true;
}
int count(int state) //統(tǒng)計(jì)該狀態(tài)下國(guó)王，即1的個(gè)數(shù)
{
int res = 0;
for(int i = 0;i < n;i ++) res += state >> i & 1;
return res;
}
int main()
{
cin >>n >> m;
for(int i = 0;i < 1 << n;i ++)
if(check(i))
{
state.push_back(i); //將合法方案存入state
cnt[i] = count(i);
}
for(int i = 0;i < state.size();i ++)
for(int j = 0;j < state.size();j ++)
{
int a = state[i], b = state[j];
if((a & b) == 0 && check(a | b)) //上下排兼容的情況
head[i].push_back(j);
}
f[0][0][0] = 1;
for(int i = 1;i <= n + 1;i ++) //枚舉每一行
for(int j = 0;j <= m;j ++) //國(guó)王數(shù)量
for(int a = 0;a < state.size();a ++) //枚舉合法方案
{
f[i & 1][j][state[a]] = 0;//要先清空,因?yàn)榈谝痪S一直在循環(huán),轉(zhuǎn)移用的 += ，不清空會(huì)用到前前階段的狀態(tài)
for(int b : head[a])
{
int c = cnt[state[a]];
if(j >= c)
f[i & 1][j][state[a]] += f[i - 1 & 1][j - c][state[b]];
//因?yàn)閟tate[a]和a呈映射關(guān)系，所也可以寫成
// f[i][j][a] += f[i - 1][j - c][b];
}
}
cout << f[n + 1 & 1][m][0] << endl;
return 0;
}C語(yǔ)言網(wǎng)提供由在職研發(fā)工程師或ACM藍(lán)橋杯競(jìng)賽優(yōu)秀選手錄制的視頻教程，并配有習(xí)題和答疑，點(diǎn)擊了解：
一點(diǎn)編程也不會(huì)寫的：零基礎(chǔ)C語(yǔ)言學(xué)練課程
解決困擾你多年的C語(yǔ)言疑難雜癥特性的C語(yǔ)言進(jìn)階課程
從零到寫出一個(gè)爬蟲的Python編程課程
只會(huì)語(yǔ)法寫不出代碼？手把手帶你寫100個(gè)編程真題的編程百練課程
信息學(xué)奧賽或C++選手的 必學(xué)C++課程
藍(lán)橋杯ACM、信息學(xué)奧賽的必學(xué)課程：算法競(jìng)賽課入門課程
手把手講解近五年真題的藍(lán)橋杯輔導(dǎo)課程