一、暴力穷举为什么不行
暴力来做的话，需要确定走的顺序，是一个(0)到(n-1)的全排列 ，假设(n=5) .就是(0)号到(4)号，共(5)个节点。
$0 1 2 3 4 $
$0 1 3 2 4 $
$0 2 1 3 4 $
$0 2 3 1 4 $
$0 3 1 2 4 $
$0 3 2 1 4 $
共(6)组，个数是((n-2)!)个，（在为首尾是固定的，其它的是全排列）
如果要暴力解决，那么每一组解都需要遍历一次所有节点的权，就是需要一重循环加上去，是(n)个，就是(n * (n-2)!)个。(n)要是(20)左右的数，就很恐怖了。
二、动态规划为什么行
动态规划从本质上讲，并没有真正算出所有的可行解是什么，而一般是计算 最大值，最小值，总方案数等，说白了，就是只计算数量，而不是真的列出来到底是哪些，举个栗子就是老师让孩子数一下(1)到(100)有多少个数，有的孩子是掰手指头一个个查，最终答案是(100),有的孩子聪明，知道(1)到(100)是(100)个数是一个道理。
三、为什么要用状态压缩
某类问题包含很多的信息，每一个信息都需要一个数组来存储。
例如：有一道题是关于(n)扇门的状态的问题，有(5)个门，(1)代表开，(0)代表关。那么用数组描述(a[1]—a[5])：分别为$0 1 1 0 1 $ 就代表 关 开 开 关 开，如果(n)是一个很大的数(10^8)，数组往往开的太大了！
所以呢，为了避免空间开太大，也为了方便程序描述状态，可以把这个状态压缩成一个十进制的数字(13)来代替，因为((13)_2=01101)。
另外，如果使用二进制描述的话，那么 左移，右移，与，或，非，异或等操作就是非常自然的，可以很灵活找出两个状态之间的交集，并集等，非常方便。
四、按DP思考问题
对于一个(4)个点的带权无向图，从点(1)到点(4)有两条路径，(1->2->3->4) 和 (1->3->2->4) 两条路径，这两条路径有共同的状态：
-
所有点都经历过一遍
-
起点终点相同
用(f[i][j]) 表示经过(i)这些点，终点是(j)的最短长度。
我们用一个(2^n)(从(0)到(2^n-1))个数(i)的每一位表示该点是否经过。
其中(i)的用例以(1-4)为例，就是如下：
(0000,0001,0010,0100,1000,0011,0101,1100,1001,1010，0110，1111,1110,1101,1011,0111) 全排列，共(16)个。
这里面有些状态是不符合条件的，我们会在后面的判断中去除掉，比如想求从(1)到(3)的所有状态，结果路径中没有出现(1)和(3)，就肯定不是合法状态。
注意，这里随着j的变化(i)的合法状态也是不一样的。
(k->j) 代表的是走的(k)到(j)这条边，就是(w[k][j])就是从(k)走到(j)的距离。
我们想要整个(f[i][j])最短，而 (w[k][j])是固定的，那么就需要前面的最短，就是(0-->k)最短
我们从(0-->j)走过的是(i)
我们从(0-->k)走的是(i-(1 << j)),这个太棒了，怎么想的啊！！！！
(f[i,j]= min(f[i,j],f[i-(1 << j),k]+a[k][j]))
五、实现代码
#include <bits/stdc++.h>
using namespace std;
const int N = 20; //好小的上限N,大的没法状态压缩实现,2^N不能太大啊！
const int M = 1 << N; //2的N次方
int w[N][N]; //邻接矩阵，记录每两个点之间的距离
int f[M][N]; //DP状态数组,记录每一步的最优解
int n; //n个结点
int main() {
//优化输入
ios::sync_with_stdio(false);
cin >> n;
//读入邻接矩阵,注意是从0~n-1
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> w[i][j];
//求最短，初始正无穷
memset(f, 0x3f, sizeof f);
// 初始化
// 从0号点出发，到达0号点，已经走过的路径就只有0这一个结点，用二进制描述的话，就只有一位，那么填1还是填0呢？
// 答案：填1，因为0这个点其实是走过了的。
f[1][0] = 0;
//枚举状态
for (int i = 0; i < (1 << n); i++)
//枚举每个节点
for (int j = 0; j < n; j++)
//这个状态中第j位是不是1,判断这个节点是不是包含在路径中,不在路径中的没有必要进行处理
if (i >> j & 1) {
//如果通过引入结点k,使得距离更短的话
for (int k = 0; k < n; k++)
//需要满足i这个路径中除去j这个点，一定要包含k这个点
if ((i - (1 << j)) >> k & 1)
f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
}
// 最终经历了所有结点，并且最后停在n-1(最后一个点，因为坐标从0开始)这个点
printf("%d", f[(1 << n) - 1][n - 1]);
return 0;
}