題目:
給定一個矩陣m,從左上角開始每次隻能向右或者向下走,最後達到右下角的位置,路徑上所有的數字累加起來就是路徑和,傳回所有的路徑中最小的路徑和。
舉例:
給定的m如下:
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0
路徑1,3,1,0,6,1,0是所有路徑中路徑和最小的,是以傳回12。
代碼實作:
方法一:
/**
* 借助m*n的輔助空間來解決問題
* @param nums
* @return
*/
public static int getMinPathSum1(int nums[][]){
if(nums == null || nums.length == 0 || nums[0] == null || nums[0].length == 0){
return 0;
}
int row = nums.length;
int col = nums[0].length;
int [][]dp = new int[row][col];
dp[0][0] = nums[0][0];
for(int i = 1; i < row; i++){
dp[i][0] = dp[i-1][0] + nums[i][0];
}
for(int j = 1; j < col; j++){
dp[0][j] = dp[0][j-1] + nums[0][j];
}
for(int i = 1; i < row; i++){
for(int j = 1; j < col; j++){
dp[i][j] = Math.min(dp[i][j-1], dp[i-1][j]) + nums[i][j];
}
}
return dp[row-1][col-1];
}
方法二:
/**
* 借助于m*1或者1*n的輔助空間
* @return
*/
public static int getMinPathSum2(int nums[][]){
if(nums == null || nums.length == 0 || nums[0] == null || nums[0].length == 0){
return 0;
}
int more = Math.max(nums.length, nums[0].length); //得到行與列的較大值為more
int less = Math.min(nums.length, nums[0].length); //得到行與列的較小值為less
boolean rowmore = more == nums.length; //行數是不是大于列數
int arr[] = new int[less]; //輔助空間僅為行或者列的最小值
arr[0] = nums[0][0];
for(int i = 1; i < less; i++){
arr[i] = arr[i-1] + (rowmore ? nums[0][i] : nums[i][0]);
}
for(int i = 1; i < more; i++){
arr[0] = arr[0] + (rowmore ? nums[i][0] : nums[0][i]);
for(int j = 1; i < less; j++){
arr[j] = Math.min(arr[j-1], arr[j]) + (rowmore ? nums[i][j]:nums[j][i]);
}
}
return arr[less-1];
}