欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

左神算法基础class8—题目7二维数组中最小路径和

程序员文章站 2022-06-03 16:09:02
...

1.题目:二维数组中最小路径和

给你一个二维数组,二维数组中的每个数都是正数,要求从左上
角走到右下角,每一步只能向右或者向下。沿途经过的数字要累
加起来。返回最小的路径和。
左神算法基础class8—题目7二维数组中最小路径和

2.暴力递归:

(1)分析

能够用递归的思路解决是因为
①寻找终止条件
如果已经到达最右下角位置:路径和就是最下角位置的值
如果在最后一行(只能向右走):下一个位置(右侧位置)到最右下角最短路径的和加上当前位置的值
如果在最后一列(只能向下走):下一个位置(下侧位置)到最右下角最短路径的和加上当前位置的值

②每一步的代价
如果向右走:代价就是右侧位置到最右下角最短路径的和
如果向下走:代价就是下侧位置到最右下角最短路径的和
取上述两者最小值,加上当前位置的值

(2)核心代码

int walk (const vector<vector<int> >& v,int i,int j)//从i、j出发 
{
	if(i == v.size() - 1 && j == v[0].size() - 1) //已经到达最右下角位置
		return v[i][j];
	if(i == v.size() - 1) 						  //在最后一行 
		return v[i][j] + walk(v,i,j + 1);		  
	if(j == v[0].size() - 1) 					  //在最后一列 
		return v[i][j] + walk(v,i + 1,j);
	int right =  walk(v,i,j + 1);//右边位置到右下角位置的最小路径 
	int down =  walk(v,i + 1,j); //下边位置到右下角位置的最小路径 
	return v[i][j] + min(right,down);
}

3.动态规划:

暴力递归中有很多重复运算,考虑缓存部分最短路径,需要的时候直接用

(1)分析

本题有重复状态,且每一步与最短路径无关无后效性问题,可以改为动态规划

左神算法基础class8—题目7二维数组中最小路径和
建立以i、j的二维数组dp
①找出需求点 ※ 为dp[0][0],
②找出基准点,最后一个位置为dp[row][col] = v[row][col];此外,最后一行和最后一列也可以求出最短路径如下图
左神算法基础class8—题目7二维数组中最小路径和
③分析每一步:当前位置最小路径是右侧位置和下侧位置最小路径的最小值
左神算法基础class8—题目7二维数组中最小路径和

(2)核心代码

int walk2 (const vector<vector<int> >& v)
{
	int row = v.size() - 1;
	int col = v[0].size() - 1;
	vector<vector<int> > dp(v.size(),vector<int>(v[0].size(),0));	//初始化dp数组 
	dp[row][col] = v[row][col];		//基础点 
	//最后一行 
	for(int j = col - 1; j >= 0; --j)
	{
		dp[row][j] = dp[row][j + 1] +  v[row][j];
	}  
	//最后一列 
	for(int i = row - 1; i >= 0; --i)
	{
		dp[i][col] = dp[i + 1][col] + v[i][col];
	} 
	//每一步 
	for(int i = row - 1; i >= 0; --i)
		for (int j = col - 1; j >= 0; --j)
		{
			dp[i][j] = min(dp[i][j + 1],dp[i + 1][j])+ v[i][j];
		}
	return dp[0][0];		//需求位置
}

4.完整代码

#include<iostream>
#include<vector>
//#include<math.h>
using namespace std;

 //递归 
int walk (const vector<vector<int> >& v,int i,int j)//从i、j出发 
{
	if(i == v.size() - 1 && j == v[0].size() - 1) //已经到达最右下角位置
		return v[i][j];
	if(i == v.size() - 1) 						  //在最后一行 
		return v[i][j] + walk(v,i,j + 1);		  
	if(j == v[0].size() - 1) 					  //在最后一列 
		return v[i][j] + walk(v,i + 1,j);
	int right =  walk(v,i,j + 1);//右边位置到右下角位置的最小路径 
	int down =  walk(v,i + 1,j); //下边位置到右下角位置的最小路径 
	return v[i][j] + min(right,down);
}

//无后效性问题,可以改为动态规划
int walk2 (const vector<vector<int> >& v)
{
	int row = v.size() - 1;
	int col = v[0].size() - 1;
	vector<vector<int> > dp(v.size(),vector<int>(v[0].size(),0));		//初始化dp数组 
	dp[row][col] = v[row][col];		//基础点 
	//最后一行 
	for(int j = col - 1; j >= 0; --j)
	{
		dp[row][j] = dp[row][j + 1] +  v[row][j];
	}  
	//最后一列 
	for(int i = row - 1; i >= 0; --i)
	{
		dp[i][col] = dp[i + 1][col] + v[i][col];
	} 
	//每一步 
	for(int i = row - 1; i >= 0; --i)
		for (int j = col - 1; j >= 0; --j)
		{
			dp[i][j] = min(dp[i][j + 1],dp[i + 1][j])+ v[i][j];
		}
	return dp[0][0];			//需求位置
}

int main()
{

	//二维初始化vector<vector<int> > v(4,vector<int>(4,0));
	//cout<<v.size()<<" " <<v[0].size();
	vector<vector<int> > v = {{ 1, 3, 5, 9 }, 
							  { 8, 1, 3, 5 }, 
							  { 5, 0, 6, 1 }, 
							  { 8, 8, 4, 0 } };
	
//	cout<<walk(v,0,0);
	cout<<walk2(v);
	return 0;
}