9.9递归和动态规划(二)——有个机器人坐在X*Y网格的左上角,只能向右、向下移动,机器人从(0,0)到(X,Y)有多少种走法

2015年8月8日 9点热度 0条评论 来源: half1_2_1

/**

 * 功能:有个机器人坐在X*Y网格的左上角,只能向右、向下移动。机器人从(0,0)到(X,Y)有多少种走法。

 *
进阶:假设有些点为“禁区”,机器人不能踏足。找出一条路径,让机器人从左上角移动到右下角。

 */

解答:
排列组合问题:共有(X+Y)!/X!Y!


进阶问题有两种方法:


方法一:

	//递归法
	/**
	 * 思路:自上而下
	 * 从终点往回走,试着找出到其相邻点的路径。
	 * @param x
	 * @param y
	 * @param path
	 * @return
	 */
	public static boolean getPath(int x,int y,ArrayList<Point> path){
		Point p=new Point(x,y);
		path.add(p);
		if(x==0&&y==0)
			return true;//找到路径
		
		boolean success=false;
		if(x>=1&&isFree(x-1,y))//向左走
			success=getPath(x-1,y, path);
		if(y>=1&&isFree(x,y-1))
			success=getPath(x,y-1,path);
		
		if(!success)
			path.add(p);//错误路径
		 
		return success;
		
	}

方法二:

<span style="white-space:pre">	</span>//动态规划
	/**
	 * 思路:缓存先前访问过的点
	 * @param x
	 * @param y
	 * @param path
	 * @param cache
	 * @return
	 */
	public static boolean getPathDP(int x,int y,ArrayList<Point> path,HashMap<Point,Boolean> cache){
		Point p=new Point(x,y);
		if(x==0&y==0)
			return true;
		
		path.add(p);
		
		if(cache.containsKey(p))
			return cache.get(p);
		
		boolean success=false;
		if(x>=1&&isFree(x-1,y))
			success=getPathDP(x-1, y, path, cache);
		if(y>=1&&isFree(x,y-1))
			success=getPathDP(x, y-1, path, cache);
		
		if(!success)
			path.add(p);//错误路径的点
		
		cache.put(p, success);//缓存结果
		
		return success;
	}
}

class Point{
	int x;
	int y;
	boolean isFree;
	
	public Point(){}
	public Point(int x,int y){
		this.x=x;
		this.y=y;
	}
}

    原文作者:half1_2_1
    原文地址: https://blog.csdn.net/shangqing1123/article/details/47360615
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。