状态压缩 $DP$ 模型 —— 最短汉密尔顿路径

问题分析：

若暴力枚举出答案，相当于对 $n$ 个点做全排列，排列完每一个点后还需要计算每条路径的长度，故复杂度为 $O(n! \cdot n)$

状态表示 $f[i][j]$：

集合：所有从 $0$ 号点走到 $j$（起点是 $0$，终点是 $j$），走过的所有点是 $i$ 的所有路径构成的集合。这里 $i$ 是压缩的状态，是一个二进制数。每个点只能走一次。
属性：Min：集合中，所包含的最短路径

举个例子，当 $i = (1110011)_{2}$ 时，对于每一位数，$0$ 表示当前这个点没有走过，$1$ 表示已经走过。

状态计算（集合划分）：

划分依据：倒数第二个点是哪个点(也就是说判断当前这个 $f[i][j]$ 状态是从哪个状态转移过来的)：$$0,\ 1,\ 2,\ …,\ n - 1$$ 例如： $2$，$f[i][j]$ 表示所有从 $0$ 走到 $j$，走过的所有点的状态是 $i$，并且倒数第二个点是 $2$ 的所有路径构成的集合

一般情况：

若倒数第二个点是第 $k$ 个点，则有：
$$ 0 == \Rightarrow ······ k = \Rightarrow j$$ 这样 $f[i][j]$ 所表示的最小路径就可以转化为 $f[i- \lbrace j \rbrace][k] + a[k][j]$ ，状态转移方程为：$$f[i][j] = f[i- \lbrace j \rbrace][k] + a[k][j]$$

最终答案即：f[(1 << n) - 1][n - 1]

时间复杂度：

一共有 $2^n \cdot n$ 个状态，每个状态的计算量为 $n$，故总时间复杂度为 $O(n^2 \cdot 2^n)$

有几点边界问题需要注意：

1. 我认为 $i$ 这个状态是不需要从 $0$ 开始枚举的，因为 $i = 0$ 时，表明此时没有走过任何一个点，方案是不存在的；进一步扩展，诸如 $f[0][j]$ 状态均不合法，因此方案数均不存在。经验证，将循环中的 $i$ 改为 $1$ 也可以AC。

2. f[1][0] = 0， 此状态表明当前还在原点 $0$ 处，路径长为 $0$，为什么不对诸如 $f[1][j]$ 的其他点进行初始化呢？原因同第一条，状态不合法，因此方案数不存在。

3. 至于为什么 $i$ 是 $1 \leq i < 1 << n$， 因为点集是 $0 \sim n - 1$ 共 $n$ 个点，表示状态的二进制数最多有 $n$ 位，且终点状态的二进制数是 $n$ 位 $1$，所以状态 $i$ 的取值应为 $1 \leq i \leq (1 << n) - 1$

4. 关于枚举倒数第二个点 $k: \ 0 \sim n - 1$ 为什么是(i - (1 << j) >> k & 1)，举个例子解释其正确性，我们来看转移方程：$f[i][j] = f[i- \lbrace j \rbrace][k] + a[k][j]$，去掉 $j$ 这个点，就是将表示走过路径的状态 $i$ 减去对应的 $j$ 点，若 $j = 2$ 表明应该减去 $0…100$，事实上也就是左移 $2$ 位，并且减去之后它的第 $k$ 位即表示 $i$ 状态的 $k$ 这个点。

   这里i >> k & 1这个位运算操作我一直都弄错了，这里的 $k$ 应该是从 $0$ 开始计数的 详见： AcWing 801. 二进制中1的个数

完整代码：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20, M = 1 << N;

int n;
int w[N][N];
int f[M][N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            cin >> w[i][j];
    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;
    for (int i = 1; i < 1 << n; i ++ )
        for (int j = 0; j < n; j ++ )
            if (i >> j & 1)
                for (int k = 0; k < n; k ++ )
                    if ((i - (1 << j)) >> k & 1)
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
    cout << f[(1 << n) - 1][n - 1] << endl;
    return 0;
}