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

问题描述：给定一个包含非负整数的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];
}