package leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.com/problems/minimum-path-sum/
 */
public class Problem64 {
    //    public int minPathSum(int[][] grid) {
    //    	int min = Integer.MAX_VALUE;
    //    	Map<String, Integer> memo = new HashMap<>();
    //    	for (int col = 0; col < grid[0].length; col++) {
    //    		min = Math.min(min, minPathSum(grid, 0, col, memo));
    //    	}
    //    	return min;
    //    }
    //    
    //    private int minPathSum(int[][] grid, int row, int col, Map<String, Integer> memo) {
    //    	if (memo.containsKey(row + "|" + col)) {
    //    		return memo.get(row + "|" + col);
    //    	}
    //    	if (grid.length-1 == row) {
    //    		return grid[row][col];
    //    	}
    //    	int val = grid[row][col];
    //    	int a = minPathSum(grid, row+1, col, memo);
    //    	int min = val + a;
    //    	if (col+1 < grid[row].length) {
    //    		int b = minPathSum(grid, row, col+1, memo);
    //    		min = Math.min(val+a,  val+b);
    //    	}
    //    	memo.put(row + "|" + col, min);
    //    	return min;
    //    }

    public int minPathSum(int[][] grid) {
        Map<String, Integer> memo = new HashMap<>();
        return minPathSum(grid, 0, 0, memo);
    }

    private int minPathSum(int[][] grid, int row, int col, Map<String, Integer> memo) {
        if (grid.length - 1 == row && grid[row].length - 1 == col) {
            return grid[row][col];
        }
        if (memo.containsKey(row + "|" + col)) {
            return memo.get(row + "|" + col);
        }
        int min = Integer.MAX_VALUE;
        if (row + 1 < grid.length) {
            int val = grid[row][col];
            int a = minPathSum(grid, row + 1, col, memo) + val;
            min = Math.min(a, min);
        }
        if (col + 1 < grid[row].length) {
            int val = grid[row][col];
            int b = minPathSum(grid, row, col + 1, memo) + val;
            min = Math.min(b, min);
        }
        memo.put(row + "|" + col, min);
        return min;
    }
}

@@ -149,984 +149,8 @@
 4 %7B%0A
-    //    public int minPathSum(int%5B%5D%5B%5D grid) %7B%0A    //    %09int min = Integer.MAX_VALUE;%0A    //    %09Map%3CString, Integer%3E memo = new HashMap%3C%3E();%0A    //    %09for (int col = 0; col %3C grid%5B0%5D.length; col++) %7B%0A    //    %09%09min = Math.min(min, minPathSum(grid, 0, col, memo));%0A    //    %09%7D%0A    //    %09return min;%0A    //    %7D%0A    //    %0A    //    private int minPathSum(int%5B%5D%5B%5D grid, int row, int col, Map%3CString, Integer%3E memo) %7B%0A    //    %09if (memo.containsKey(row + %22%7C%22 + col)) %7B%0A    //    %09%09return memo.get(row + %22%7C%22 + col);%0A    //    %09%7D%0A    //    %09if (grid.length-1 == row) %7B%0A    //    %09%09return grid%5Brow%5D%5Bcol%5D;%0A    //    %09%7D%0A    //    %09int val = grid%5Brow%5D%5Bcol%5D;%0A    //    %09int a = minPathSum(grid, row+1, col, memo);%0A    //    %09int min = val + a;%0A    //    %09if (col+1 %3C grid%5Brow%5D.length) %7B%0A    //    %09%09int b = minPathSum(grid, row, col+1, memo);%0A    //    %09%09min = Math.min(val+a,  val+b);%0A    //    %09%7D%0A    //    %09memo.put(row + %22%7C%22 + col, min);%0A    //    %09return min;%0A    //    %7D%0A%0A
     

Update problem 64