package cn.xf.algorithm.ch08DynamicProgramming;import java.util.ArrayDeque;import java.util.Deque;import org.junit.Test;import cn.xf.algorithm.ch08DynamicProgramming.vo.CompareIndexVo;import cn.xf.algorithm.ch08DynamicProgramming.vo.ResultVo;/** * 硬币搜集问题 *  * 在n*m格木板中放有一些硬币，每格的硬币数目最多为一个。在木板左上方的一个机器人需要搜集 * 尽可能多的硬币并把他们带到右下方的单元格，每一步，机器人可以从当前的位置向右移动一格 * 或者向下移动一格，当机器人遇到一个有硬币的单元格的时，就会将这枚硬币搜集起来 *  * . *  * @版权：福富软件 版权所有 (c) 2017 * @author xiaof * @version Revision 1.0.0 * @see: * @创建日期：2017年8月4日 * @功能说明： * */public class CollectCoins { 	//硬币收集的时候，我们 从结果状态开始看，当搜集当前硬币的时候，只有两种方式，从上往下搜集，或者从左向右搜集	//也就是当前f[i,j] = max{f[i, j - 1], f[i - 1, j]},初始化第一行和第一列，从第二行和列开始遍历	//就可以动态规划所有的中间状态，最后获取最后的位置的地方的和，即便是搜集到的最大的和,并且过程的路径可以输出	public ResultVo robotCoinCollection(int coins[][]) {		if(coins == null || coins.length <= 0 || coins[0].length <= 0) {			return null;		}//		Deque deque = new ArrayDeque();		//创建存储硬币动态规划数组		int allRows = coins.length;		int allColumns = coins[0].length;		int resultF[][] = new int[allRows][allColumns];		//首先初始化，起始位置和第一行		resultF[0][0] = coins[0][0];//		String curPath = "<0,0>";//		deque.push(curPath);		for(int j = 1; j < allColumns; ++j) {			resultF[0][j] = resultF[0][j - 1] + coins[0][j];		}		//双循环，遍历整个地图		for(int i = 1; i < allRows; ++i) {			//顺路初始化每一行的第一个			resultF[i][0] = resultF[i - 1][0] + coins[i][0];			//遍历所有列			for(int j = 1; j < allColumns; ++j) {				//选择路径比较大的进入队列				//当搜集当前硬币的时候，只有两种方式，从上往下搜集，或者从左向右搜集,那么就是把从上过来的和从右边过来的进行比较之后，选择硬币搜集比较大的位置为路径				CompareIndexVo compareIndexVo = getMax(resultF[i][j - 1], resultF[i - 1][j]);				resultF[i][j] = compareIndexVo.getResult() + coins[i][j];				//路径设计//				if(compareIndexVo.getIndex() == 1) {//					//如果是第一个参数比较大//					curPath = "<" + i +", " + (j - 1) + ">";//				} else {//					curPath = "<" + (i - 1) +", " + j + ">";//				}//				deque.push(curPath);			}		}		ResultVo resultVo = new ResultVo();		resultVo.setResultF(resultF);//		resultVo.setDeque(deque);		return resultVo;	}		public static CompareIndexVo getMax(int a, int b) {		CompareIndexVo vo = new CompareIndexVo();		if(a < b) {			vo.setResult(b);			vo.setIndex(2);		} else {			vo.setResult(a);			vo.setIndex(1);		}				return vo;	}		@Test	public void test1() {		CollectCoins collectCoins = new CollectCoins();		int coins[][] = {{0,0,0,0,1,0},{0,1,0,1,0,0},{0,0,0,1,0,1},{0,0,1,0,0,1},{1,0,0,0,1,0}};		ResultVo resultVo = collectCoins.robotCoinCollection(coins);		//输出路径，以及最大值		System.out.println("搜集到的最大硬币是：" + resultVo.getResultF()[coins.length - 1][coins[0].length - 1]);		System.out.print("路径是：");		//循环从结果数组中查询出对应的路径		int curI = 0; int curJ = 0;		int resultF[][] = resultVo.getResultF();		System.out.print("<0,0>");		while(curI < coins.length && curJ < coins[0].length) {			//比较向下和向右的大小			int goDown; int goRight;			int i,j;			if(curI == coins.length -1) {				//如果i极限				goDown = -1;			} else {				goDown = resultF[curI + 1][curJ];			}						if(curJ == coins[0].length -1) {				//如果i极限				goRight = -1;			} else {				goRight = resultF[curI][curJ + 1];			}			//只能向右或向下走 !(goDown == -1 && goDown == -1)			//两个同时到了末尾，就不用输出了			if(!(goDown == -1 && goDown == -1)) {				if(goDown > goRight) {					//向下走,如果是因为向右到头le					System.out.print(" = <" + (curI + 1) + "," + curJ + ">");					curI += 1;				} else {					System.out.print(" = <" + (curI) + "," + (curJ + 1) + ">");					curJ += 1;				}			} else {				//两个同时到头，跳出循环				break;			}		}	}	}