<commit_before>/**
 *	Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
 *
 *	For example, given the following triangle
 *	[
 *      [2],
 *     [3,4],
 *	  [6,5,7],
 *	 [4,1,8,3]
 *	]
 *	The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
 *
 *	Author: matao
 *
 */

import java.util.ArrayList;
import java.util.List;

public class Triangle {

	// Dynamic Programming from up to bottom
	public static int minimumTotal1(List<List<Integer>> triangle) {
		if(triangle == null || triangle.size() == 0) {
			return 0;
		}
		int n = triangle.size();
		int[][] sum = new int[n][n];

		sum[0][0] = triangle.get(0).get(0);

		for (int i = 1; i < n; i++) {
			for (int j = 0; j <= i; j++) {
				if (j == 0 || j == i) {
					sum[i][j] = sum[i-1][j] + triangle.get(i).get(j);
				} else {
					sum[i][j] = Math.min(sum[i-1][j-1], sum[i-1][j]) + triangle.get(i).get(j);
				}
			}
		}
		return minItemOfLineN(sum);
    }

    private static int minItemOfLineN(int[][] sum) {
    	int n = sum.length;
    	int min = sum[n-1][0];
    	for(int i = 1; i < sum[n-1].length; i++) {
    		if(min < sum[n-1][i]) {
    			min = sum[n-1][i];
    		}
    	}
    	return min;
    }
<commit_msg>add dynamic programming solution<commit_after>/**
 *	Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
 *
 *	For example, given the following triangle
 *	[
 *      [2],
 *     [3,4],
 *	  [6,5,7],
 *	 [4,1,8,3]
 *	]
 *	The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
 *
 *	Author: matao
 *
 */

import java.util.ArrayList;
import java.util.List;

public class Triangle {

	// Dynamic Programming from up to bottom
	public static int minimumTotal1(List<List<Integer>> triangle) {
		if(triangle == null || triangle.size() == 0) {
			return 0;
		}
		int n = triangle.size();
		int[][] sum = new int[n][n];

		sum[0][0] = triangle.get(0).get(0);

		for (int i = 1; i < n; i++) {
			for (int j = 0; j <= i; j++) {
				if (j == 0) {
					sum[i][j] = sum[i-1][0] + triangle.get(i).get(0);
				} else if (j == i){
					sum[i][j] = sum[i-1][i-1] + triangle.get(i).get(i);
				} else {
					sum[i][j] = Math.min(sum[i-1][j-1], sum[i-1][j]) + triangle.get(i).get(j);
				}
			}
		}
		return minItemOfLineN(sum);
    }

    private static int minItemOfLineN(int[][] sum) {
    	int n = sum.length;
    	int min = sum[n-1][0];
    	for(int i = 1; i < sum[n-1].length; i++) {
    		if(min > sum[n-1][i]) {
    			min = sum[n-1][i];
    		}
    	}
    	return min;
    }

{'fraction_non_alphanumeric': 0.19474085365853658, 'fraction_numerical': 0.03048780487804878, 'mean_word_length': 2.4358638743455496, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4848017', 'n_tokens_mistral': 1179, 'n_tokens_neox': 1063, 'n_words': 284}