<—麻烦点一下这个好看的东东，谢谢

推荐一下$\color{#FF00FF}{算法基础课 第五章 动态规划全题解（正在完善）}$

题目描述

给定一张 n 个点的带权无向图，点从 $ 0∼n−1 $ 标号，求起点 $0$ 到终点 $n−1$ 的最短 $Hamilton$ 路径。

$Hamilton$ 路径的定义是从 $0$ 到 $n−1$ 不重不漏地经过每个点恰好一次。

输入格式

第一行输入整数 $n$。

接下来 $n$ 行每行 $n$ 个整数，其中第 $i$ 行第 $j$ 个整数表示点 $i$ 到 $j$ 的距离（记为 $a[i,j]$）。

对于任意的 $x$,$y$,$z$，数据保证 $a[x,x]=0$，$a[x,y]=a[y,x]$ 并且 $a[x,y]+a[y,z]≥a[x,z]$。

输出格式

输出一个整数，表示最短 Hamilton 路径的长度。

数据范围

$1≤n≤20$
$0≤a[i,j]≤10^7$

输入样例：

5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0

输出样例：

18

这里解释一下输入样例

在矩阵中的每一个数表示的是从点 $i$ 到 $j$ 的距离。

算法1

(状态压缩DP) $O(2^n n^2)$

可以说是状态表示思路极明确，但是代码实现…

发现以前写的题解不是很容易理解，这里再详细解释一下可能出现的问题。

$Q$：$f[i][j]$中的$i$和$j$具体表示为什么？

$A$：

• $i$为一个二进制数，每一位分别表示是否经过该位上的点

  例如：101就是表示这条路径经过了$0$号点和$2$号点，但不经过$1$号点。

• $j$表示从$0$号点开始，最后在$j$号点落脚的最短路径。

$Q$：为什么更新状态转移方程时需要将$i$减去$2^j$？

$A$：从上面的问题我们知道，$i$的每一位分别表示是否经过该位上的点。
并且从图中更新状态转移的意思是：将$0 \rightarrow j$的路径更新为$0 \rightarrow k \rightarrow j$（取$min$计算，这里简写了）。

所以状态转移方程为：

$$f[i][j] = min(f[i][j],f[i - 2^j][k] + w[k][j])$$

在调用$f[i - 2^j][k]$时，这段路径的落脚点为$k$点，不一定经过$j$点，所以需要把$j$位改成0（因为$i$表示的二进制数中$f[i][j]$这段路径经过了$j$，第$j$位为$1$）

$Q$：最后的答案为什么存在$f[2^n - 1][n - 1]$中？

$A$：我们知道$2^n$表示$\underbrace{111…1}_{n位}$，因为我们题目中是求$0 \rightarrow {n - 1}$的最短哈密顿距离。
在我们的代码中是从$0$遍历到$2^n - 1$（你可以看到在代码中是for(int i = 0;i < 1 << n;i ++)），也就是说，我们的$2^n$其实是存在$2^n - 1$中的。

参考文献

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 20,M = 1 << N;
//解释一下1 << N：因为i是二进制数，表示从0到当前点的状态，所以每个点都有两个状态0和1，所以是2的N次方
int n;
int w[N][N]; //每条边的权重
int f[M][N]; //表示从0到j，走过的点是i的所有路径
int main(){
    scanf("%d",&n);
    for(int i = 0;i < n;i ++){
        for(int j = 0;j < n;j ++){
            scanf("%d",&w[i][j]);
        }
    }
    memset(f,0x3f,sizeof f);
    f[1][0] = 0; //0为起点，所以为0
    for(int i = 0;i < 1 << n;i ++){ // 遍历所有方案000...00 ~ 1111...111
        for(int j = 0;j < n;j ++){ //j表示走到的哪一点
            if(i >> j & 1){ //如果i的j为1，说明到达过这个点
                for(int k = 0;k < n;k ++){ //k表示走到j这个点之前，以k为终点的最短距离
                    if((i - (1 << j)) >> k & 1){ //i除去j这个点后包含k这个点
                        f[i][j] = min(f[i][j],f[i - (1 << j)][k] + w[k][j]); //状态转移，前面图1有详细讲解哦~
                    }
                }
            }
        }
    }
    printf("%d\n",f[(1 << n) - 1][n - 1]); //输出答案
    // (1 << n) - 1表示：有n个1，也就是所有的点都走完了
    // n - 1表示：终点
    // 合起来就是所有的点都走完的方案，最后落脚在n - 1这个点
    return 0;
}