leetcode.943. 最短超级串(dp,TSP)

943. 最短超级串

每两个字符串连边，边的长度等价于这两个字符串的重和长度，问题：就是要求一条简单路径走过所有的点，并且长度最长。
设表示第个点到集合的最长路径,表示这个集合内的点的 。
所以转移就是 ，从小到大。

class Solution {
public:
    bool equ(string a,string b){return a==b;}
    string cal(string a,string b){
        int n=a.size(),m=b.size();
        int pos=0;
        for (int len=min(n,m);len;len--){
            if(equ(a.substr(n-len),b.substr(0,len))){
                pos=len;break;
            }
        }
        return a+b.substr(pos);
    }
    string shortestSuperstring(vector<string>& A) {
        int dp[13][1<<12|1]={0};
        int dis[13][13],path[13][1<<12|1];
        int n=A.size();if(n==1)return A[0];
        for (int i=0;i<n;i++){
            for (int j=0;j<n;j++){
                if(i==j)continue;
                dis[i][j] =A[i].size()+A[j].size()-cal(A[i],A[j]).size();
            }
        }
        for (int j=1;j<(1<<n);j++){
            for(int i=0;i<n;i++){
                if(j&(1<<i))continue;
                for(int k=0;k<n;k++){
                    if((j&(1<<k))&&i!=k){
                        if(dp[i][j]<=dis[i][k]+dp[k][j^(1<<k)]){
                            dp[i][j]=dis[i][k]+dp[k][j^(1<<k)];
                            path[i][j]=k;
                        }
                    }
                }
            }
        }
        int p=0,S=(1<<n)-1;
        for(int i=0;i<n;i++)if(dp[i][S^(1<<i)]>dp[p][S^(1<<p)])p=i;
        vector<int>v;
        while(S){
            v.push_back(p);
            S^=1<<p;
            p=path[p][S];
        }
        string s=A[v[0]];
        for(int i=1;i<n;i++)s=cal(s,A[v[i]]);
        return s;
    }
};