假设n个旅馆距离原点的距离存放在数组arr[0. . .n-1]中，punish[0. . .n-1]表示在某个旅馆停留时所受的的惩罚的最小值。当然在第一个旅馆停留时所受到的惩罚为0，即punish[0]=0。若i>0,则在第i个旅馆停留时所受到的惩罚的最小值符合递推式：
package org.xiu68.ch06.ex5;
public class Ex6_2 {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr=new int[]{200,300,450,600,700,850};
minPunish(arr);
/*
punish[0]=0
punish[1]=10000
punish[2]=12500
punish[3]=15000
punish[4]=25000
punish[5]=27500
*/
}
/*
* arr[0]~arr[n-1]为n个旅店,值为距离原点的距离
*/
public static void minPunish(int[] arr){
if(arr==null || arr.length==0)
return;
int[] punish=new int[arr.length]; //记录停留在第i个旅店所受到总的最小惩罚值
punish[0]=0; //在第一个旅店受到的惩罚为0
System.out.println("punish[0]=0");
for(int i=1;i<arr.length;i++){
int twoPlacePunish=200-(arr[i]-arr[i-1]);
punish[i]=(int) (punish[i-1]+Math.pow(twoPlacePunish, 2));
for(int j=i-2;j>=0;j--){
if(arr[i]-arr[j]>200)
break;
int temp=punish[j]+(200-(arr[i]-arr[j]))^2;
if(punish[i]>temp)
punish[i]=temp;
}
System.out.println("punish["+i+"]="+punish[i]);
}//for
}
}