左神算法基础class8—题目7二维数组中最小路径和
程序员文章站
2022-06-03 16:09:02
...
1.题目:二维数组中最小路径和
给你一个二维数组,二维数组中的每个数都是正数,要求从左上
角走到右下角,每一步只能向右或者向下。沿途经过的数字要累
加起来。返回最小的路径和。
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)分析
本题有重复状态,且每一步与最短路径无关无后效性问题,可以改为动态规划
建立以i、j的二维数组dp
①找出需求点 ※ 为dp[0][0],
②找出基准点,最后一个位置为dp[row][col] = v[row][col];此外,最后一行和最后一列也可以求出最短路径如下图
③分析每一步:当前位置最小路径是右侧位置和下侧位置最小路径的最小值
(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;
}