如果我们用g[i][j]表示A[i]后面接上A[j]需要添加的字符的话：
- 比如A[i] = abc, A[j] = bcd, g[i][j] = 1
- A[i] = abc, A[j] = def, g[i][j] = 3
那么建图之后，这道题就转化成了TSP问题(Travelling Salesman Problem)。简而言之，我们需要求得最短的路径，并且只通过所有节点一次。TSP问题是NP hard的，dynamic programming是一个解决的思路，但是我们仍然需要遍历所有的状态。
用dp[i][j]表示当前已经visited过的点用i的二进制为表示，并且最后一个visit的节点是j的情况下的最短路径。那么我们可以得到递推方程:
- dp[i ^ (1 << k)][k] = min(dp[i][j] + g[j][k]), where k is not visited, j can be every node visited in i
我们根据这个递推公式求得最后的结果即可。注意题目需要我们输出最后的string，所以我们需要用另一个数组parent[i][j]记录状态i j情况下最优解的前置节点。假设输入有N个string，最后的时间复杂度就为O(n^2 * 2^n)，代码如下:
No comments:
Post a Comment