首页 > 代码库 > Leetcode 动态规划 Minimum Path Sum

Leetcode 动态规划 Minimum Path Sum

本文为senlie原创,转载请保留此地址:http://blog.csdn.net/zhengsenlie


Minimum Path Sum

 Total Accepted: 15789 Total Submissions: 50645My Submissions

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.


题意:给定一个 m * n 的网格,网格中有非负的数字。
一个机器人要从左上角走到右下角,每次只能向下或向右移动一个位置,
找出一条总和最小的路径,返回最小值
思路1:记忆化搜索
使用一个两维 minPathSums[i][j]记录 (i,j)到(m,n)的总和最小的路径的值
然后使用dfs 枚举
复杂度:时间O(2^n) 空间O(n)


思路2:dp
设置状态为f[i][j],表示到达网格(i,j)的总和最小的路径的值,则状态转移方程为
f[i][j] = min(f[i - 1][j] + f[i][j - 1]) + grid[i][j]
实现的时候,可以只用一个一维的数组minPathSums[j]表示外循环第i次迭代内循环第j次迭代对应的paths值
在还没更新状态时,minPathSums[j]对应f[i - 1][j]; minPathSums[j - 1]对应f[i][j - 1]
复杂度:时间 O(n),空间O(n)


vector<vector<int> > minPathSums;
vector<vector<int> > _grid;
int m, n;
int _minPathSum(int x, int y){
	if(x >= m || y >= n) return INT_MAX;
	if(minPathSums[x][y] >= 0) return minPathSums[x][y];
	if(x == m - 1 && y == n - 1) return _grid[x][y];
	return minPathSums[x][y] = _grid[x][y] + min(_minPathSum(x + 1, y), _minPathSum(x, y + 1) );
}
int minPathSum(vector<vector<int> > &grid){
	m = grid.size();
	n = grid[0].size();
	minPathSums = vector<vector<int> >(m, vector<int>(n, -1));
	_grid = grid;
	return _minPathSum(0, 0);
}




int minPathSum(vector<vector<int> > &grid){
	int m = grid.size(), n = grid[0].size();
	vector<int> minPathSums(n, INT_MAX); //下面的循环中 i 是从0开始的,它前面的就是 i = -1的情况,所以应该是 INT_MAX, 表示不可达
	minPathSums[0] = 0;
	for(int i = 0; i < m; ++i){
		minPathSums[0] += grid[i][0];
		for(int j = 1; j < n; ++j){
			minPathSums[j] = min(minPathSums[j], minPathSums[j - 1]) + grid[i][j ];
		}
	}
	return minPathSums[n - 1];
}


Leetcode 动态规划 Minimum Path Sum