这道题在黑书里面介绍的非常详细，我这里贴一下使用滚动数组来优化的代码。
用dp[x][y][z]存，当第z步的时候左脚在x,右脚在y的情况。
dp[x][y][z] = min（dp[a[i]][y][i + 1] + doit（x , a[i]） , dp[x][a[i]][i + 1] + doit（y , a[i]）） ;
#define N 100005
int dp ;
int a[N] ;
int doit（int a ,int b） {
if（a == b）return 1 ;
if（a == 0 || b == 0）return 2 ;
if（a == 1） {
if（b == 2 || b == 4 || b == 0）return 3 ;
return 4 ;
}
if（a == 2） {
if（b == 3 || b == 1 || b == 0）return 3 ;
return 4 ;
}
if（a == 3） {
if（b == 2 || b == 4 || b == 0）return 3 ;
return 4 ;
}
if（a == 4） {
if（b == 1 || b == 3 || b == 0）return 3 ;
return 4 ;
}
}
int main（） {
while（cin 》 a[0] , a[0]） {
int num = 1 ;
while（1） {
cin 》 a[num] ;
num ++ ;
if（a[num - 1] == 0）break ;
}
num -- ;
for （int i = 0 ; i < 2; i ++ ）{
for （int j = 0 ; j < 5 ; j ++ ）{
for （int k = 0 ; k < 5; k ++ ）{
dp[j][k][i] = inf ;
}
}
}
for （int i = 0 ; i < 5 ; i ++ ）dp[i][a[num - 1]][num % 2] = dp[a[num - 1]][i][num % 2] = 0 ;
for （int i = num - 1 ; i >= 0 ; i -- ） {
for （int j = 0 ; j < 5 ; j ++ ） {
for （int k = 0 ; k < 5 ; k ++ ） {
dp[j][k][i % 2] = min（dp[a[i]][k][（i + 1） % 2] + doit（j , a[i]） , dp[j][a[i]][（i + 1） % 2] + doit（k ,a[i]）） ;
}
}
}
cout 《 dp[0][0][0] 《 endl;
}
return 0 ;
}
POJ 3311 裸TSP --08.07
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define Max 2505
#define ll long long
#define PI acos（-1.0）
#define inf 0x2fffffff
#define LL（x） （ x 《 1 ）
#define bug puts（"here"）
#define PII pair<int,int>
#define RR（x） （ x 《 1 | 1 ）
#define mp（a,b） make_pair（a,b）
#define mem（a,b） memset（a,b,sizeof（a））
#define REP（i,s,t） for（ int i = （ s ） ; i <= （ t ） ; ++ i ）
using namespace std;
inline void RD（int &ret） {
char c;
do {
c = getchar（）；
} while（c < '0' || c > '9'） ;
ret = c - '0';
while（（c=getchar（）） >= '0' && c <= '9'）
ret = ret * 10 + （ c - '0' ）；
}
inline void OT（int a） {
if（a >= 10）OT（a / 10） ;
putchar（a % 10 + '0'） ;
}
#define N 12
int Map[N][N] ;
int n ;
int dp[1 《 N][N] ;
int main（） {
while（cin 》 n , n）{
for （int i = 0 ; i < n + 1 ; i ++ ）{
for （int j = 0 ; j < n + 1 ; j ++ ）{
cin 》 Map[i][j] ;
}
}//floyd,注意MAP[I][J] != MAP[J][I]
for （int i = 0 ; i < n + 1 ; i ++ ）{
for （int j = 0 ; j < n + 1 ; j ++ ）{
for （int k = 0 ; k < n + 1 ; k ++ ）{
Map[i][j] = min（Map[i][j] , Map[i][k] + Map[k][j]） ;
}
}
}
for （int i = 0 ; i < （1 《 （n + 1）） ; i ++）{
for （int j = 0 ; j < n + 1 ; j ++ ）dp[i][j] = inf ;
}//从0出发，回到0.可重复走路径
dp[0][0] = 0 ;
for （int i = 0 ; i < （1 《 （n + 1）） ; i ++ ）{
for （int j = 0 ; j < n + 1 ; j ++ ）{
if（i & （1 《 j） == 0）continue ;
for （int k = 0 ; k < n + 1 ; k ++ ）{
if（k == j）continue ;//所以这里不需要判断if（i & （1 《 k））continue ;
int tt = i | （1 《 k） ;
dp[tt][k] = min（dp[i][j] + Map[j][k] , dp[tt][k]） ;
}
}
}
cout 《 dp[（1 《 （n + 1）） - 1][0] 《 endl;
}
return 0 ;
}
POJ 1185 炮兵阵地 --08.07
经典的状压dp.
网上的解释很多也很详细，这里就不多解释了。