<commit_before>package leetcode;

/**
 * https://leetcode.com/problems/minimum-path-sum/
 */
public class Problem64 {
    public int minPathSum(int[][] grid) {
    	// TODO: to be implemented
        return 0;
    }
    
    public static void main(String[] args) {
		Problem64 prob = new Problem64();
		int[][] grid = new int[][] {
			new int[]{1, 9, 4, 7},
			new int[]{6, 2, 1, 5},
			new int[]{1, 3, 8, 2}
		};
		System.out.println(prob.minPathSum(grid));
	}
}<commit_msg>Solve problem 64<commit_after>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;
    }
}
{'fraction_non_alphanumeric': 0.18082191780821918, 'fraction_numerical': 0.01487279843444227, 'mean_word_length': 1.7964989059080962, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 9, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4136685', 'n_tokens_mistral': 959, 'n_tokens_neox': 921, 'n_words': 214}