首页 > 其他 > 详细

Unique Paths

时间:2014-05-24 21:58:16      阅读:367      评论:0      收藏:0      [点我收藏+]

题目:给定一个由参数m,n表示行数和列数而形成的2维表格,以左上为出发点,右下为目的地,每次只能向右走一步,或者向下走一步,算出总共存在多少不同的到达路径。

分析;这个问题的递归属性是很明显的,因为无论向右走还是向下走,到达一个新的位置,这时就变成了在该新位置到达目的地有多少不同的路径。其次,向右走和向下走是不同的路径,最终的结果应该是二者的和。

递归的返回条件:n = 1 或 m = 1, 对于这种没选择的单方向,只能是返回1。

int uniquePaths_recursion(int m, int n) {
	if( 1 == n || 1 == m)
		return 1;
	return uniquePaths_recursion(m - 1, n) + uniquePaths_recursion(m, n - 1);
}

在m = 23,n = 12的时候就超时了。

当解题思路正确,且递归可以实现,只是时间超时的时候,就是该考虑dp的时候了,dp与递归明显的优势就是会记录子问题的状态,不用重复的计算子问题。这就节省了很多的时间。

 dp[ i, j ] :表示从出发点到达(i,j)点不同的路径数。

状态转移方程:dp[ i, j ] = dp[ i - 1, j] + dp[ i, j - 1]。其意义是,到达(i,j) 可以是通过上一位置向右移动或上一位置向下移动完成的。

初始条件:dp[ i, 0] = 1, dp[ 0, j ] = 1。因为在第一行的所有位置,只能是上一位置向右走完成的,同理,第一列的所有位置只能是上一位置向下移动完成的,这里将出发点也设置为1了,没关系,我们不会用到出发点的信息。

返回值:dp[m,n]。

通过观察状态转移方程,当前的位置只跟上一位置有关,跟上上一次的位置都是无关的,而上一位置只能是在其上面或在其左面,所以我们可以定义两个变量,而无需定义m*n的表。

int uniquePaths_dp(int m, int n){
	if(1 == n || 1 == n)
		return 1;
	//initial 
	vector<int> pre_dp( n, 1);
	
	for (int i = 1; i < m; ++i)
	{
		vector<int> cur_dp(n, 1);

		for (int j = 1; j < n; ++j)
		{
			cur_dp[j] = cur_dp[j - 1] + pre_dp[j];
		}
		pre_dp = cur_dp;
	}
	return pre_dp[n - 1];
}


Unique Paths,布布扣,bubuko.com

Unique Paths

原文:http://blog.csdn.net/shiquxinkong/article/details/26709041

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!