状态压缩dp的概念

状压 dp 是动态规划的一种，通过将状态压缩为二进制数来处理复杂的集合问题。

方案数

例题： 农夫有一块长方形土地，化成 n 行 m 列的方格。他准备种玉米，养牛（在一个格子内），不过有些格子很贫瘠，不适合种玉米。还有，牛不喜欢在一起吃，所以牛不能放在相邻的格子里，给出这块地的情况求出农夫有多少种种玉米的方案。所有方格都不种玉米也算一种方案。
解决： 时间复杂度
用 dp[i][j] 表示第 i 行采取编号为 j 的方案时前 i 行可以得到的可行方案总数。
从第 i-1 行转移到第 i 行的状态转移方程：
把最后一行的相加就得到了答案：

// poj 3254（http://poj.org/problem?id=3254）
#include<iostream>
#include<stdio.h>

using namespace std;

const int mod = 1e8;

long long dp[13][1<<12], num[13];

int main() {
    int n, m; scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++ i) {
        for(int j = 1; j <= m; ++ j) {
            int k; scanf("%d", &k);
            num[i] = num[i] << 1 | k;          // 二进制压缩
        }
        num[i] = num[i] ^ (1<<m) - 1;          // 全部取反
    }
    for(int i = 0; i < (1<<m); ++ i) {
        if (i & (i<<1) | i & num[1]) continue; // 不相邻且土地肥沃
        dp[1][i] = 1;
    }
    for(int i = 2; i <= n; ++ i) {
        for(int j = 0; j < (1<<m); ++ j) {
            if (j & (j << 1) | j & num[i]) continue;  // 不相邻且土地肥沃
            for(int k = 0; k < (1<<m); ++ k) {
                if (j & k) continue;                  // 上下也要不相邻
                (dp[i][j] += dp[i-1][k]) %= mod;
            }
        }
    }
    long long res = 0;
    for(int i = 0; i < (1<<m); ++ i) {
        res = (res + dp[n][i]) % mod;
    }
    printf("%d\n", res);
    return 0;
}

旅行商问题（TSP）

有 n 个城市，已知任何两个城市之间的距离（或者费用），一个旅行商从某城市出发，经过每一个城市并且只经过一次，最后回到出发的城市，输出最短（或者费用最少）的线路。
DP状态设计如下：
时间复杂度
假设已经访问过的城市集合是 i，当前所在城市是 j，用 dp[i][j]表示从 j 出发访问剩余的所有城市最后回到起点的路径费用总和最小值。状态转移方程如下：
// 已访问过所有城市回到起点

注：经过每一个城市至少一次至多两次时把二进制改为三进制，经过每一个城市至少一次时加一个floyd即可。

// hdu 5418 （http://acm.hdu.edu.cn/showproblem.php?pid=5418）
// 此题为经过城市至少一次【最短路TSP】
#include<bits/stdc++.h>

using namespace std;

const int maxn = 20;
const int inf = 0x3f3f3f3f;

int graph[maxn][maxn];
int dp[1<<maxn][maxn];

void init(int n) {
    for(int i = 1; i <= n; ++ i) {
        for(int j = i; j <= n; ++ j) {
            if (i == j) graph[i][j] = 0;
            else graph[i][j] = graph[j][i] = inf;
        }
    }
    for(int i = (1<<n)-1; i >= 0; -- i) {
        for(int j = 1; j <= n; ++ j) {
            dp[i][j] = inf;
        }
    }
}

void floyd(int n) { 
    for(int k = 1; k <= n; ++ k) {
        for(int i = 1; i <= n; ++ i) {
            for(int j = 1; j <= n; ++ j) {
                graph[i][j] = min(graph[i][k] + graph[k][j], graph[i][j]);
            }
        }
    }
}

void tsp(int n) {
    dp[(1<<n)-1][1] = 0;
    for(int i = (1<<n)-2; i >= 0; -- i) {
        for(int j = 1; j <= n; ++ j) {
            for(int k = 1; k <= n; ++ k) {
                if (i >> k-1 & 1) continue;
                dp[i][j] = min(dp[i|1<<k-1][k] + graph[j][k], dp[i][j]);
            }
        }
    }
    printf("%d\n", dp[0][1]);
}

int main() {
    int T; scanf("%d", &T);
    while(T --) {
        int n, m; scanf("%d%d", &n, &m);
        init(n);
        for(int i = 1; i <= m; ++ i) {
            int u, v, w; scanf("%d%d%d", &u, &v, &w);
            if (graph[u][v] > w) graph[u][v] = graph[v][u] = w;
        }
        floyd(n);
        tsp(n);
    }
    return 0;
}

专题

hdu 3001 （http://acm.hdu.edu.cn/showproblem.php?pid=3001）【三进制TSP】