汽车加油问题

就是。。经典问题么。。

有很多个加油站，汽车最远跑多少公里，问你在哪几个地方加油可以让加油次数最少

每个加油站距离不同

import java.util.LinkedList;import java.util.List;public class CarAndGas {/** * @param args */private static int MAX_DISTANCE = 10;private static int[] distance = {8,3,5,2,4,7,3,3,2,4,6,7};//private static boolean[] choose = {false,false,false,false,false,false,false,false,false,false,false,false,false};public static void main(String[] args) {List<Integer> list = needGas(0,0);System.out.println(list);}//position is the next stationprivate static List<Integer> needGas(int position,int extra) {if(distance[position]+extra>MAX_DISTANCE) {//in this case the car can not reach.....return null;}if (position == distance.length-1){return new LinkedList<Integer>();}//if choose current station, the problem is.....List<Integer> withGas = needGas(position+1,0);withGas.add(position);//if choose not to put gasList<Integer> noGas = needGas(position+1,distance[position]+extra);if (noGas == null ||withGas.size()<noGas.size()) {return withGas;} else {return noGas;}}}