我们要分析出几个概念。左边的第i个节点，可以与右边某个未被链接的节点j相连，这样i,j两个点都算被连接，一箭双雕。但是，i也可以与右边某个已经被链接的节点j相连，这种情况下j虽然看上去被链接了两次有点浪费，但是如果i-j这条边的权重很小，那么用很小的代价仅仅把i也拉进去也可能是实惠的。
如此看来，选择将i和右边的哪些点相连，并没有什么可以贪心的策略。所以这就让我们尝试用状态压缩的技巧来尝试所有i的链接方法。
令dp[i][state]表示左边前i个节点连接了右边的点集state时，所需要的最小代价。点集state就是“压缩的状态”，本质是一个二进制bit组，每一位bit表示所代表的节点是否已经被连接。
在解dp[i][state]这个问题时，我们的突破口就是第i个节点的决策。之前讨论过，它可以连接右边任意个未被连接的点，目的是最高效的使用这些边将两边都未被访问的节点都连起来。但是有时候，并没有足够小的边能满足这个要求，那么这个时候只能退而求其次，随便找条最小的边能把i连上就可以了。注意，这两种分支是不可能重合的，即不可能i既与右边还没连接的点相连，也与右边已经连接的点相连；这种情况下，后者的操作是每必要的。
对于前者的操作，那么i的决策对应的就是连接了state里面的某个非零子集，我们称之为subset。那么它的前驱状态就是dp[i-1][state-subset]，在本轮需要加上i与subset连接的代价。我们需要遍历所有可能的subset，找到dp[i-1][state-subset]+cost[i][subset]的最小值。
对于后者的操作，那么i连接的就是右边的某个已经被连接过的节点（必然是对i而言代价最小的边）。此策略的前驱状态就是dp[i-1][state]，因为i所连接的点并不是一个未曾方位过的点。
所以大致的框架就是：
for (int i=0; i<m; i++)
for (int state=0; state<(1<<n); state++)
{
for (int subset : state)
dp[i][state] = dp[i-1][state-subset] + cost[i][subset]
dp[i][state[ = dp[i-1][state] + minCost[i]
}注意对于state的遍历嵌套subset的遍历，时间复杂度并不是 2^N * 2^N，而是3^N。你可以想象，对于每一个bit，在外、里两层的状态只可能是10,11,00。
所以总的时间复杂度是: M*3^N*N，其中最后一个N是对subset的分解来累加i的总cost。
对于遍历state的子集，有高效的循环方法需要掌握：
for (int subset=state; subset>0; subset=(subset-1)&state)PS：有同学问，第二种情况的代码是不是应该加一层条件：只找state里面存在的点。这么写确实是更严谨的。不过也可以认为不必要。第二种情况只有在第一种情况的最优解仍不够优秀的情况下才有意义。如果第二种得到的更优解对应的是一个未被访问的右边的点，那么这个点必然也会在第一种情况内被覆盖到。