|
题目链接：https://leetcode-cn.com/problems/minimum-path-sum/
题意：
给定一个包含非负整数的?m?x?n?网格?grid?，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
方法：动态规划?
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
//只能向下或者向右移动一步
int row = grid.size();//记录有几行
int col = grid[0].size();//记录有几列
vector<vector<int>> dp(row,vector<int>(col));//动态规划数组，dp[i][j]表示左上角到(i,j)的最短路径
dp[0][0] = grid[0][0];//定义初始状态
for(int i=1;i<row;i++)//枚举第一列的dp值
{
dp[i][0] = dp[i-1][0]+grid[i][0];
}
for(int i=1;i<col;i++)//枚举第一行的dp值
{
dp[0][i] = dp[0][i-1]+grid[0][i];
}
for(int i=1;i<row;i++)//枚举除了第一行的每一行
{
for(int j=1;j<col;j++)//枚举除了第一列的每一列
{
dp[i][j] = grid[i][j]+min(dp[i][j-1],dp[i-1][j]);//取左侧和上方的最小值加上当前的值
}
}
return dp[row-1][col-1];//返回右下角那个点的dp，一定就是1从起点到重点的最短路径
}
};
?方法二：效率低，A*算法?
struct node{//定义结构体节点
int x;//横坐标
int y;//纵坐标
int dis;//起点到该点的距离
int f;//启发式测度
node()
{
}
node(int _x,int _y,int _dis){//构造函数
x = _x;//给x赋值
y = _y;//给y赋值
dis = _dis;//给dis赋值
}
bool operator<(const node& a) const//重载运算符
{
return f > a.f; //小顶堆
}
};
class Solution {
private:
int computeF(vector<vector<int>>& grid,node node1)//计算启发式测度
{
int row = grid.size();//获取行数
int col = grid[0].size();//获取列数
int minV = 0;//最小值
if(node1.x+1<row)//可以往下走
{
minV = min(grid[node1.x+1][node1.y],minV);
}
if(node1.y+1<col)//可以往右走
{
minV = min(grid[node1.x][node1.y+1],minV);
}
return minV;//返回最小值
}
public:
int minPathSum(vector<vector<int>>& grid) {
int row = grid.size();//获取行数
int col = grid[0].size();//获取列数
vector<vector<int>> isVisited(row,vector<int>(col,0));//表示节点是否被访问过
priority_queue<node> q;//定义一个队列
node v0(0,0,grid[0][0]);//定义初始节点
q.push(v0);//将初始节点插入队列
node select;//选中节点
while(true)
{
select = q.top();//取队首元素
q.pop();//队首元素出队列
if(select.x==row-1&&select.y==col-1) break;//找到终点就结束
if(select.x+1<row&&!isVisited[select.x+1][select.y])//下面有点，且未被访问
{
isVisited[select.x+1][select.y] = 1;//访问过该节点了
node dow = node(select.x+1,select.y,select.dis+grid[select.x+1][select.y]);//定义一个节点，并进行初始化
dow.f = dow.dis+computeF(grid,dow);//计算启发式测度
q.push(dow);//往队列插入该节点
}
if(select.y+1<col&&!isVisited[select.x][select.y+1])//右边有点，且未被访问
{
isVisited[select.x][select.y+1] = 1;//标记访问过该节点
node rig = node(select.x,select.y+1,select.dis+grid[select.x][select.y+1]);//定义一个节点，并进行初始化
rig.f = rig.dis+computeF(grid,rig);//计算启发式测度
q.push(rig);//往队列插入该节点
}
}
return select.dis;//返回终点计算出的距离
}
};
?
|