雙調(diào)tsp
/*
dp[i][j],，表示從i連到0，再?gòu)?連到j(luò)，（注意，i>j，且并沒(méi)有相連。）
有兩種連接方法，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步，第一個(gè)人橫著走了j步，第二個(gè)人橫著走了k步,容易確定豎著走了多少步，這道題可以重復(fù)走，所以枚舉時(shí)就不需要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