31 动态规划和递归解最小路径和

2023-12-17 22:30:13

问题描述:给定一个包含非负整数的m×n网格,请找出一条从左上角到右下角的路径,使得路径上的数字综合为最小;

递归求解思路:每一个递归函数都可以向下和向右两种,在进行判断时需要进行判断越界问题,在到达最后一格的时候,加入PriorityQueue minHeap的最小堆中,最后返回最小堆中的元素。

public void getMinPath(int [][]matrix,int rowIndex ,int columnIndex,int pathSum,PriorityQueue<Integer> minHeap)
{
if(rowIndex==matrix.length||columnIndex==matrix[0].length)
return;
if(rowIndex==matrix.length-1&&columnIndex==matrix[0].length-1)
{
minHeap.add(minHeap+matrix[rowIndex][columnIndex]);
return;
}
getMinPath(matrix,rowIndex+1,columnIndex,pathSum+matrix[rowIndex][columnIndex],minHeap);
getMinPath(matrix,rowIndex,columnIndex+1,pathSum+matrix[rowIndex][columnIndex],minHeap);

}
public int GetMinPath(int [][]matrix)
{
PriorityQueue<Integer>minHeap=new PriorityQueue<>();
getMinPath(matrix,0,0,0,minHeap);
return minHeap.poll();
}

动态规划求解,定义dp[i][j]表示从[0][0]到[i][j]的最小路径
?

public getMinPath(int [][]matrix)
{
int [][]dp=new int[matrix.length][matrix[0].length];
dp[0][0]=matrix[0][0];
for(int i=1;i<matrix.length;i++)
{
for(int j=1;j<matrix[i].length;j++)
{
dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+matrix[j][j];
}
}
return dp[matrix.length-1][matrix[0].length-1];
}

文章来源:https://blog.csdn.net/qq_52299902/article/details/135049941
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。