<commit_before>package com.learning.ads.dynamicprogramming;

public class MatrixChainOrder {

	public class Result {
		int finalScalarMuls;
		String parenthesizedChain;
	}

	/**
	 * Complexity: O(n^3)
	 * 
	 * @param sizes
	 * @return
	 */
	public Result calculateMultiplications(int[] sizes) {
		int n = sizes.length - 1;
		int[][] dp = new int[n + 1][n + 1];
		int[][] paths = new int[n + 1][n + 1];
		Result result = new Result();
		calculateMultiplications(sizes, dp, paths);
		StringBuilder s = new StringBuilder();
		prepareOptimalChain(paths, 1, n, s);
		result.finalScalarMuls = dp[1][n];
		result.parenthesizedChain = s.toString();
		return result;
	}

	/**
	 * Complexity: O(n^3)
	 * 
	 * @param sizes
	 * @return
	 */
	public Result calculateMultiplicationsRec(int[] sizes) {
		int n = sizes.length - 1;
		int[][] dp = new int[n + 1][n + 1];
		int[][] paths = new int[n + 1][n + 1];
		Result result = new Result();
		calculateMultiplicationsRec(sizes, dp, paths, 1, n);
		StringBuilder s = new StringBuilder();
		prepareOptimalChain(paths, 1, n, s);
		result.finalScalarMuls = dp[1][n];
		result.parenthesizedChain = s.toString();
		return result;
	}

	private int calculateMultiplicationsRec(int[] sizes, int[][] dp, int[][] paths, int i, int j) {
		if (i == j) {
			return 0;
		}<commit_msg>Changing complexity<commit_after>package com.learning.ads.dynamicprogramming;

public class MatrixChainOrder {

	public class Result {
		int finalScalarMuls;
		String parenthesizedChain;
	}

	/**
	 * Complexity: O(n^3)
	 * 
	 * @param sizes
	 * @return
	 */
	public Result calculateMultiplications(int[] sizes) {
		int n = sizes.length - 1;
		int[][] dp = new int[n + 1][n + 1];
		int[][] paths = new int[n + 1][n + 1];
		Result result = new Result();
		calculateMultiplications(sizes, dp, paths);
		StringBuilder s = new StringBuilder();
		prepareOptimalChain(paths, 1, n, s);
		result.finalScalarMuls = dp[1][n];
		result.parenthesizedChain = s.toString();
		return result;
	}

	/**
	 * Complexity: Ω(n^3)
	 * 
	 * @param sizes
	 * @return
	 */
	public Result calculateMultiplicationsRec(int[] sizes) {
		int n = sizes.length - 1;
		int[][] dp = new int[n + 1][n + 1];
		int[][] paths = new int[n + 1][n + 1];
		Result result = new Result();
		calculateMultiplicationsRec(sizes, dp, paths, 1, n);
		StringBuilder s = new StringBuilder();
		prepareOptimalChain(paths, 1, n, s);
		result.finalScalarMuls = dp[1][n];
		result.parenthesizedChain = s.toString();
		return result;
	}

	private int calculateMultiplicationsRec(int[] sizes, int[][] dp, int[][] paths, int i, int j) {
		if (i == j) {
			return 0;
		}
{'fraction_non_alphanumeric': 0.1545524100994644, 'fraction_numerical': 0.013771996939556235, 'mean_word_length': 3.771897810218978, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, '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': '6542643', 'n_tokens_mistral': 1004, 'n_tokens_neox': 886, 'n_words': 247}