64.最小パスと

タイトルの説明
非負の整数を含むmxnメッシュを指定します.左上から右下に向かうパスを見つけて、パスの数値の合計が最小になります.
説明:毎回1歩下または右に移動するしかありません.
例:

  :
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
  : 7
  :      1→3→1→1→1      。

暴力再帰の考え方
1.各位置の右と下の結果を求めることができ、毎回最小の加算を選択すればよい.
Javaコード実装

    public int minPathSum(int[][] grid) {
        return minPathSum(grid,0,0);
    }

    private int minPathSum(int[][] grid,int i,int j,int[][] memory) {
        if(i == grid.length)
            return Integer.MAX_VALUE-grid[i-1][j];
        if(j == grid[0].length)
            return Integer.MAX_VALUE-grid[i][j-1];
        if(i == grid.length-1 && j == grid[0].length-1)
            return grid[i][j];
        int path1 = grid[i][j]+minPathSum(grid,i+1,j,memory);
        int path2 = grid[i][j]+minPathSum(grid,i,j+1,memory);
        int curPath = Math.min(path1,path2);
        return curPath;
    }

メモ方法
1.暴力法は同じ位置の答えを何度も計算することができるので、計算した答えを記憶することができ、その位置の答えが計算されていることを発見すれば、結果を再帰する必要がなく、再帰の回数を大幅に減らすことができます.
Javaコード実装

    public int minPathSum(int[][] grid) {
        int[][] memory = new int[grid.length][grid[0].length];
        return minPathSum(grid,0,0,memory);
    }

    private int minPathSum(int[][] grid,int i,int j,int[][] memory) {
        if(i == grid.length)
            return Integer.MAX_VALUE-grid[i-1][j];
        if(j == grid[0].length)
            return Integer.MAX_VALUE-grid[i][j-1];
        if(i == grid.length-1 && j == grid[0].length-1)
            return grid[i][j];
        if(memory[i][j] != 0)
            return memory[i][j];
        int path1 = grid[i][j]+minPathSum(grid,i+1,j,memory);
        int path2 = grid[i][j]+minPathSum(grid,i,j+1,memory);
        int curPath = Math.min(path1,path2);
        memory[i][j] = curPath;
        return curPath;
    }

ダイナミックプランニング
1.以上の2つの方法で状態遷移方程式をまとめることができる:dp(i,j)=grid(i,j)+min(dp(i+1,j),dp(i,j+1))2.2次元配列を設定してdpの結果を格納し、dp[0][0]を結果として返す.
Javaコード実装

    public int minPathSum(int[][] grid) {
        int[][] res = new int[grid.length+1][grid[0].length+1];
        for (int i = grid.length-1; i >= 0 ; i--) {
            for (int j = grid[0].length - 1; j >= 0; j--) {
                if (i == grid.length - 1 && j == grid[0].length - 1) {
                    res[i][j] = grid[i][j];
                    continue;
                }
                //       
                if (i == grid.length - 1) {
                    res[i][j] = grid[i][j] + res[i][j + 1];
                    continue;
                }
                //       
                if (j == grid[0].length - 1) {
                    res[i][j] = grid[i][j] + res[i + 1][j];
                    continue;
                }
                res[i][j] = Math.min(grid[i][j] + res[i][j + 1], grid[i][j] + res[i + 1][j]);
            }
        }
        return res[0][0];
    }