矩陣最小路徑和練習

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

給定一個矩陣map及它的行數n和列數m，請傳回最小路徑和。保證行列數均小于等于100.

測試樣例：

[[1,2,3],[1,1,1]],2,3

傳回：4

這個也不難，對于格子中的每一個點，走到這一個點的最短路徑隻有兩種情況，從上面下走，或者從左邊向右走，用一個矩陣dp[n][m]記錄從開始點走到每一個位置的最短路徑，轉移公式如下：

dp[i][j]=min(dp[i][j−1],dp[i−1][j])+map[i][j]

代碼就很容易寫了

class MinimumPath {
public:
    int getMin(vector<vector<int> > map, int n, int m) {
        int dp[n][m];
        dp[][]=map[][];
        for(int i=;i!=m;++i)
            dp[][i]=dp[][i-]+map[][i];
        for(int i=;i!=n;++i)
            dp[i][]=dp[i-][]+map[i][];

        for(int i=;i!=n;++i){
            for(int j=;j!=m;++j)
                {
                dp[i][j]=min(dp[i][j-],dp[i-][j])+map[i][j];
            }
        }
        return dp[n-][m-];
    }
};