假设n个旅馆距离原点的距离存放在数组arr[0. . .n-1]中，punish[0. . .n-1]表示在某个旅馆停留时所受的的惩罚的最小值。当然在第一个旅馆停留时所受到的惩罚为0，即punish[0]=0。若i>0,则在第i个旅馆停留时所受到的惩罚的最小值符合递推式：
1 package org.xiu68.ch06.ex5; 2 3 public class Ex6_2 { 4 5 public static void main(String[] args) { 6 // TODO Auto-generated method stub 7 int[] arr=new int[]{200,300,450,600,700,850}; 8 minPunish(arr); 9 10 /* 11 punish[0]=0 12 punish[1]=10000 13 punish[2]=12500 14 punish[3]=15000 15 punish[4]=25000 16 punish[5]=27500 17 */ 18 19 } 20 /* 21 * arr[0]~arr[n-1]为n个旅店,值为距离原点的距离 22 */ 23 24 public static void minPunish(int[] arr){ 25 if(arr==null || arr.length==0) 26 return; 27 int[] punish=new int[arr.length]; //记录停留在第i个旅店所受到总的最小惩罚值 28 punish[0]=0; //在第一个旅店受到的惩罚为0 29 System.out.println("punish[0]=0"); 30 for(int i=1;i<arr.length;i++){ 31 int twoPlacePunish=200-(arr[i]-arr[i-1]); 32 punish[i]=(int) (punish[i-1]+Math.pow(twoPlacePunish, 2)); 33 34 for(int j=i-2;j>=0;j--){ 35 if(arr[i]-arr[j]>200) 36 break; 37 38 int temp=punish[j]+(200-(arr[i]-arr[j]))^2; 39 if(punish[i]>temp) 40 punish[i]=temp; 41 } 42 System.out.println("punish["+i+"]="+punish[i]); 43 }//for 44 45 } 46 47 }