筆試算法模拟題精解之“矩陣最小路徑和”

原文連結

題目名稱

矩陣最小路徑和

題目位址

https://developer.aliyun.com/coding/34

題目描述

概述：

給定一個矩陣，大小為m，從左上角開始每次隻能向右走或者向下走，最後達到右下角的位置。路徑中所有數字累加起來就是路徑和，傳回所有路徑的最小路徑和。

示例1

比如輸入矩陣為

4 1 5 3
3 2 7 7
6 5 2 8
8 9 4 5           

最小路徑為：

23           

方法一

動态規劃思想：先求簡單值在逐漸遞推求複雜值，後面的值通過前面的結果來求得。

保證每一步的最小值進行存儲即可

思路：

建立一個矩陣dp（大小也是M*M），該矩陣是從上往下，從左往右記錄每一步的結果的，目前的結果可以根據該矩陣上面和左邊最小的值來獲得。

public class Top34 {  

    public int solution(int[][] m) {  
        if(m==null){  
            return 0;  
        }  
        if(m.length==0){  
            return 0;  
        }  
        int[][] dp = new int[m.length][m[0].length];  

        dp[0][0] = m[0][0];  
        //先計算第一行  
        for (int i = 1; i < m.length; i++) {  
            dp[i][0] = dp[i-1][0]+m[i][0];  
        }  
        //計算第一列  
        for (int i = 1; i < m[0].length; i++) {  
            dp[0][i] = dp[0][i-1]+m[0][i];  
        }  

        //從上->下，左->右 計算目前位置的最小值  
        for (int i = 1; i < m.length; i++) {  

            for (int j = 1; j < m[0].length; j++) {  
                dp[i][j] = Math.min(dp[i][j-1],dp[i-1][j]) + m[i][j];  
            }  

        }  

        return dp[m.length-1][m[0].length-1];  
    }  
}             

時間複雜度O(M

*

M)，空間複雜度O(M

*

M)

消耗

執行用時：7ms

執行記憶體：9kb

動态規劃求解問題的特點：

• 從暴力遞歸中來
• 把每一個子問題的解記錄下來，避免重複計算
• 把暴力遞歸的過程，抽象成了狀态表達
• 并且存在化簡狀态表達，使其更加簡潔

方法二

暴力求解。

public class Top34_2 {  

    public int solution(int[][] m) {  
        if(m==null){  
            return 0;  
        }  
        if(m.length==0){  
            return 0;  
        }  
        return minPath(m,0,0);  
    }  


    /**  
     * 暴力遞歸方式求解最短路徑問題  
     * @param array 二維數組  
     * @param i  目前走到的行  
     * @param j  目前走到的列  
     * @return  
     */  
    private static int minPath(int[][] array, int i, int j){  
        //當i的值為array.length - 1并且j的值為array[0].length  - 1時表示走到了右下角  
        if(i == array.length - 1 && j == array[0].length  - 1){  
            //走到了右下角則直接傳回右下角的數值  
            return array[i][j];  
        }  

        //當i的值為array.length - 1并且j的值不為array[0].length - 1時，隻能往右走  
        if(i == array.length - 1 && j != array[0].length - 1){  
            return array[i][j] + minPath(array, i ,j + 1);  
        }else if(i != array.length - 1 && j == array[0].length - 1){  
            //當i的值不為array.length - 1并且j的值為array[0].length - 1時，隻能往下走  
            return array[i][j] + minPath(array, i + 1, j);  
        }  

        //否則既可以向下走也可以向右走，此時選取路徑最短的那個  
        return array[i][j] + Math.min(minPath(array, i, j + 1), minPath(array, i + 1, j));  
    }  
}             

時間複雜度O(2^M)

執行記憶體：6kb

暴力遞歸求解問題的特點：

• 把問題轉化為規模縮小了的同類問題的子問題
• 有明确的不需要繼續進行遞歸的條件
• 有當得到了子問題的結果之後的決策過程
• 不記錄每一個子問題的解

與汝俱進。

作者 | 谙憶