解决思路：

        假设当前为一个规模为n且开始结点为0号结点的旅行商问题，那么，我们所要解决的问题可以转化为将0与{0，1，2，3…n}的有向（与集合中的顺序不一定一致）序列与0相连的最小值。假设这个最小值为k与0相连的情况下产生的，那么，我们又可以将问题分解为{0，1，2，…k-1，k+1，…n}的最优与k相连解加上k与0相连的距离耗费……综上所述，该问题可以划分成最优子问题的形式，故存在动态规划解法。

       基于以上分析思考，我们可以将集合用二进制数来表示，其中每一个二进制位标识一个结点，为1则表示该结点已在集合中，为0则表示该位不在集合中。将0号结点首先内置在每一个集合中。我们构造一个n*(2^(n-1))的矩阵作为dp数组，通过对该数组的填写完成对本问题最优解的寻找。

       依据以上的分析，我们可以得到该解法的dp矩阵填写方式如下：

        1.当集合中仅有一个元素时，初始化该列的第0行元素为该点到0号节点的距离。其余位置，若无效则填0，若有效则仅可将i号结点与j对应的节点（假定为k）相连，然后将k与0号结点相连。

        2.普通位置的结点，遍历j中对应集合含有的元素，假定为kx，若存在kx==i,则证明i已在集合中，该位置无效，填0。若不存在kx==i，则遍历kx，求d=a[i][kx] +dp[k][1<<(kx-1)^j]中的最小值，填到dp数组对应位置。

程序代码：

#include <iostream>
#include <string.h>
using namespace std;

int **a,**dp, n, m, bestc;
int tsp()
{
    int k, t, mind, d, kl, flag;
    if(n<=1) return 0;
//当集合中仅有一个元素时，初始化该列的第0行元素为该点到0号节点的距离
    for(int j=1, i=1; i<n; i++,j<<=1)
        dp[0][j]=a[0][i];    
    for(int j=1; j<m; j++)
    {
        for(int i=0; i<n; i++)
        {
            if(i==0)
            {
                //已经初始化的位置，无需再次填写
                if(dp[i][j]!=0)
                {
                    flag=1;
                    continue;
                }

            }
            k=0; t=j; mind=0x7f7f7f7f;
      //当集合中仅有一个元素时，初始化该列未初始化的位置，若无效则填0，
      //若有效则仅可将i号结点与j对应的节点（假定为k）相连，然后将k与//0号结点相连。
            if(flag==1)
            {
                while( !(t&1) )
                {k++;t=t>>1;} k++;
                if(i==k) dp[i][j]=0;
                else dp[i][j]=dp[0][j]+a[i][k];
                continue;
            }
 //普通位置的结点，遍历j中对应集合含有的元素，假定为kx，
//若存在kx==i,则证明i已在集合中，该位置无效，填0。
//若不存在kx==i，则遍历kx，求d=a[i][kx]+dp[k][1<<(kx-1)^j]中的最小值，填到dp数组对应位置
            while(t)
            {
                k++;
                if(k==1) kl=1;
                else kl=kl<<1;
                if(t&1)
                {
                    if(k==i)
                    {
                        mind=0;
                        break;
                    }
                    d=a[i][k]+dp[k][kl^j];
                    if(d<mind) mind=d;
                }
                t=t>>1;
            }
            dp[i][j]=mind;
        }
        flag=0;
    }
    return dp[0][m-1];
}

int main()
{
    cin>>n;
    m=1<<(n-1);
    a=new int *[n];
    dp=new int *[n];
    for(int i=0; i<=n; i++)
    {
        a[i]=new int [n];
        dp[i]=new int [m];
        memset(dp[i],0,m*sizeof(int));
    }
    for(int i=0; i<n; i++)
    {
        a[i][i]=0;
        for(int j=i+1; j<n; j++)
        {
            cin>>a[i][j];
            a[j][i]=a[i][j];
        }
    }
    //调用函数进行dp矩阵的填写
    bestc=tsp();
    cout<<bestc<<endl;

    return 0;
}

时间复杂度分析：

        该算法的主题部分在于函数tsp()，在此前的准备工作中，邻接矩阵的读入费时为 。在tsp()函数中，首先执行dp数组的初始化，填写j标识单个元素（除0位置元素外）存在于数组中的列的首行元素，该过程的时间复杂度为O(n)，接下来进行两层for循环，对dp数组的每一个位置进行填写。其中，根据我们之前的算法设计过程可知，dp数组的大小为n行2^(n-1)列。在填写数据的过程中，需要对j进行不断地右移取数操作，来进行将i号点加入该集合的最小距离花费，因此该过程的时间复杂度为 。填完dp数组，tsp的功能就完成了。综合以上分析，动态规划法解决本实验问题的时间复杂度为 。