LintCode:最小パスと

最小パスと
非負の整数のみを含むm*nメッシュを指定し、左上から右下に数字と最小のパスを見つけます.
LintCode:最小パスと
構想一:万能の列挙

m行、n列の行列、左上から右下に進むには、(m-1)ステップを下に移動し、(n-1)ステップを右に移動し、(m+n-2)ステップを合計すると、パスの総数はC(m+n-2、m-1)ステップとなる.

m,nは小さい場合に実行可能であり,大きい場合には実行不可能である.

構想二:動的計画

dp[i][j]は、左上からgrid[i][j]に到達する最小値を表す.

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + a[i][j]

上からdp[i-1][j]+grid[i][j]

左からdp[i][j-1]+grid[i][j]

初期値

dp[0][0] = grid[0][0]

dp[0][j>0] = dp[0][j-1] + grid[0][j]

dp[i>0][0] = dp[i-1][0] + grid[i][0]

複雑度:時間O(m*n)、空間O(m*n)

class Solution {
public:
    /** * @param grid: a list of lists of integers. * @return: An integer, minimizes the sum of all numbers along its path */
    int minPathSum(vector<vector<int> > &grid) {
        // write your code here
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int> > dp(m, vector<int>(n));
        for (int i=0; i<m; i++){
            for (int j=0; j<n; j++){
                if (i==0){
                    if(j==0){
                        dp[i][j] = grid[i][j];
                    }
                    else{
                        dp[i][j] = dp[i][j-1] + grid[i][j];
                    }
                }
                else if(j==0){
                    dp[i][j] = dp[i-1][j] + grid[i][j];
                }
                else{
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
                }
            }
        }
        return dp[m-1][n-1];

    }
};

dp空間最適化

dp[i][j]はdp[i-1][j]、dp[i][j-1]のみに関連する

対i毎に、順方向ループj

前のdp[j-1]が新しいのか、dp[j]が古いのか

dp[j]=min(dp[j-1],dp[j]+a[i][j]更新

空間複雑度O(n)、時間複雑度O(m*n)

class Solution {
public:
    /** * @param grid: a list of lists of integers. * @return: An integer, minimizes the sum of all numbers along its path */
    int minPathSum(vector<vector<int> > &grid) {
        // write your code here
        int m = grid.size();
        int n = grid[0].size();
        vector<int > dp(n);
        for (int i=0; i<m; i++){
            for (int j=0; j<n; j++){
                if (i==0){
                    if(j==0){
                        dp[j] = grid[i][j];
                    }
                    else{
                        dp[j] = dp[j-1] + grid[i][j];
                    }
                }
                else if(j==0){
                    dp[j] = dp[j] + grid[i][j];
                }
                else{
                    dp[j] = min(dp[j-1], dp[j]) + grid[i][j];
                }
            }
        }
        return dp[n-1];

    }
};

参考資料
七月アルゴリズム公開授業実戦動態計画