【算法设计与分析基础】20、动态规划-硬币搜集问题

题目:

在n*m格木板中放有一些硬币,每格的硬币数目最多为一个。在木板左上方的一个机器人需要搜集
尽可能多的硬币并把他们带到右下方的单元格,每一步,机器人可以从当前的位置向右移动一格
 或者向下移动一格,当机器人遇到一个有硬币的单元格的时,就会将这枚硬币搜集起来

解题:

硬币收集的时候,我们 从结果状态开始看,当搜集当前硬币的时候,只有两种方式,从上往下搜集,或者从左向右搜集
也就是当前f[i,j] = max{f[i, j - 1], f[i - 1, j]},初始化第一行和第一列,从第二行和列开始遍历
就可以动态规划所有的中间状态,最后获取最后的位置的地方的和,即便是搜集到的最大的和,并且过程的路径可以根据动态规划中间数组输出

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;
			}
		}
	}

}

  

结果:

时间: 08-06

【算法设计与分析基础】20、动态规划-硬币搜集问题的相关文章

算法设计与分析基础(第3版)读书笔记(及几处翻译上的错误~~)

算法设计与分析基础(第3版) p16 in-place翻译为'在位'?'就地'更合适点 p38 amortized应翻译为'均摊','摊销'这个词简直莫名其妙(可能因为翻译是做算法交易导致的?) p64 迭代优于递归(迭代始终是增量式的,而递归就没办法增量了,除非能够dump整个运行时栈) p73 通过算法可视化得到一个更好的非递归算法(人的图像认知直觉思维?) p79 验证一个拓扑是环.星.还是团?(这个地方有点意思,因为我想到了动态的Verify) p87 凸包问题:从数据结构上讲,Set<

【算法设计与分析基础】大整数乘法

#include<iostream> #include<string> #include<time.h> #include<stdlib.h> #include<sstream> using namespace std; class BigDecimal{ private: int max(int a,int b){//获取两数中的最大值 return a^((a^b) & -(a<b)); } public: string n;

【算法设计与分析基础】关灯游戏

① R.java  用于存储一些全局变量 package lightoff; public class R { /* public static int lightCondition[][] = { {1,0,0,1,1}, {1,0,0,1,1}, {1,0,0,1,1}, {1,0,0,1,1}, }; */ public static int lightCondition[][] = { {1,1,1,1}, {1,1,1,1}, {1,1,1,1}, {1,1,1,1}, }; //灯面

【算法设计与分析基础】19、字符串匹配算法

package cn.xf.algorithm.ch07inputEnhancement; import java.util.HashMap; import java.util.List; import java.util.Map; import org.junit.Test; /** * * 功能:字符串匹配算法,(还有一种叫KMP算法的,也是很经典的算法,就是比较复杂) * * 第一步:对于给定的长度为m的模式和在模式文本中用到的字母表,按照上面的描述构造移动表 * 第二步:将模式与文本的开

【算法设计与分析基础】16、高斯消元法

package cn.xf.algorithm.ch06ChangeRule; import java.util.ArrayList; import java.util.List; import org.junit.Test; import cn.xf.util.GenericPair; /** * * 功能:高斯消元法,也就是多元数据矩阵,依次吧每列的其他行数据消去为0,然后求出一个元的解,然后就可以根据这个数据来递推出其他元的解 * @author xiaofeng * @date 2017

【算法设计与分析基础】17、堆

以数组来存放堆数据 package cn.xf.algorithm.ch06ChangeRule; import java.util.ArrayList; import java.util.List; import org.junit.Test; /** * * 功能:堆的构造 * 1.堆可以定义为一颗二叉树,树的节点包含键,并且满足一下条件 * 1) 树的形状要求:这棵二叉树是基本完备的(完全二叉树),树的每一层都是满的,除了最后一层最右边的元素可能缺位 * 2) 父母优势,堆特性,每一个节点

【算法设计与分析基础】18、霍纳法则

产生随机数 package cn.xf.algorithm.ch02; import java.util.ArrayList; import java.util.List; /** * 生产随机数 * @author xiaof * */ public class Random { /** * 生产一个随机数的数列 * @param n 生成n个数列 * @param m 数据在0和m-1之间 * @param seed 随机初始种子 * @param a 参数 * @param b 参数 *

【算法设计与分析基础】22、最优二叉查找树

package cn.xf.algorithm.ch08DynamicProgramming; import java.util.Arrays; import org.junit.Test; import cn.xf.algorithm.ch08DynamicProgramming.vo.ResultVo; /** * 最优二叉树问题 * * 思路:根据最优二叉树的问题就是查找对应的节点的比较次数的期望值保持最小 * 最优二叉查找树的期望搜索代价保持最小 * 例如:一颗树有节点{k0,k1,k2

【算法设计与分析基础】23、堆排序-2

package cn.xf.algorithm.ch09Greedy.util; import java.util.ArrayList; import java.util.List; /** * 堆构造以及排序 * * .功能:堆的构造 * 1.堆可以定义为一颗二叉树,树的节点包含键,并且满足一下条件 * 1) 树的形状要求:这棵二叉树是基本完备的(完全二叉树),树的每一层都是满的,除了最后一层最右边的元素可能缺位 * 2) 父母优势,堆特性,每一个节点的键都要大于或者等于他子女的键(对于任何叶