题目:空间内有n个点，p0,p1...pn-1, 你的任务是把它们配对成n/2对,n是偶数.
使得配对的距离和最小,n<=20.
思路： 以前的DP，在做了当前决策以后，剩余的问题依旧是独立的.
但是,分析一下这道题.
假设我从第一个点 i 开始配对, 假设和j配对, 那么接下来的任务是在全集S中排除i,j，即S-i-j中继续匹配.
很明显这个问题比较麻烦, 比如0和4匹配, 然后在1....n里继续匹配, 但是又要考虑4已经被匹配过了,这种状态该怎么描述.
用以前简单的d[i]表示从i开始的匹配是不足够的，体现不出剩余未匹配的集合包括哪些结点.
这就是所谓的集合DP,采用二进制来表示集合,二进制对应的整数就可以运用到DP的数组下标上了.
假设一共有4个点等待我们去匹配.
初始时, 1 1 1 1 , 来表示集合S, 这是一个二进制串,对应整数15. 右边是二进制的低位, 对应的顶点编号是 3 2 1 0.
我们先拿3匹配一个点, 假设匹配1， 那么未匹配的集合为： 0 1 0 1, 还有2和0未匹配. 我们就用2去匹配0
集合S变成0 0 0 0, 匹配完成.
这只是一个特定的决策方案, 每次匹配都可以有多种可能, 剩余的集合就会很多样.
这也是一个最优子结构问题, 集合S的最小费用匹配, 等于 各种匹配的费用+S-i-j中最小费用匹配.
S-i-j不会比S大, 与父问题没有关联, 所以可以使用DP . 从解空间树上来看, 孩子没有通向父亲的回路.
这样匹配下去, 集合S终将缩减为S=0, 即全部匹配结束 .
所以我们设d[S]表示集合S的最小费用匹配.
d[S]=min{ dist[i][j] + d[S-i-j] } ,这里的S-i-j是集合的差运算,不是减法运算. 具体实现时使用二进制^运算进行操作.
刚开始,也许会想,对于集合S,得穷举所有的i,j匹配组合.
但是,仔细想一下吧. 你在当前S中穷举那么多情况, 还不如只穷举一种情况, 反正子问题终将完成所有的匹配.
所以,只要固定一个元素i, 变化j, 找出这些匹配下的最优值就可以了. 每一层都如此做, 就保证了当前层也可以这么做.