双调tsp
/*
dp[i][j],，表示从i连到0，再从0连到j，（注意，i>j，且并没有相连。）
有两种连接方法，i与i-1相连；i与i-1不相连。
dp[i][j]=dp[i-1][j]+d[i][i-1];
dp[i][i-1]=min(dp[i-1][j]+d[j][i]);
*/
dp[0][0]=0;dp[1][0]=d[1][0];
for(int i=2;i<=n;i++){
dp[i][i-1]=DMAX;
for(int j=0;j<i-1;j++){
dp[i][j]=dp[i-1][j]+d[i][i-1];
dp[i][i-1]=min(dp[i][i-1],dp[i-1][j]+d[j][i]);
}
}
hdu 3322 poj 2677
poj 2964
dp[i][j][k]表示走了i步，第一个人横着走了j步，第二个人横着走了k步,容易确定竖着走了多少步，这道题可以重复走，所以枚举时就不需要j<k，而相同地方算一次
则dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-1][k],dp[i-1][j][k-1],dp[i-1][j-1][k-1])
hdu 3376