package com.leetcode.dynamicprogram;

import java.util.AbstractCollection;

import java.util.List;

/**

* Created by charles on 1/31/17.

* 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).

*/

public class Triangle_120 {

/**

* Bottom-Up DP, start from bottom row,

* State : dp[i][j] is min pathsum at jth node on ith row

* function: dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j];

* init: bottom

* answer : dp[0][0]

*/

public int minimumTotalSpaceOptimize(List<List<Integer>> triangle) {

int n = triangle.size();

int[] dp = new int[n + 1];

for (int i = n - 1; i >= 0; i--) {

for (int j = 0; j < triangle.get(i).size(); j++) {

dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);

}

}

return dp[0];

}

public int minimumTotal(List<List<Integer>> triangle) {

int n = triangle.size();

int[][] dp = new int[n + 1][n + 1];

for (int i = n - 1; i >= 0; i--) {

for (int j = 0; j <= i; j++) {

dp[i][j] = Math.min(dp[i + 1][j], dp[i+1][j+1]) + triangle.get(i).get(j);

}

}

return dp[0][0];

}

public int minimunTotalTopDown(List<List<Integer>> triangle) {

if (triangle == null || triangle.size() == 0) {

return -1;

}

if (triangle.get(0) == null || triangle.get(0).size() == 0) {

return -1;

}

// state : dp[i][j] = minimum path value from 0,0 to i,j

int n = triangle.size();

int[][] dp = new int[n][n];

// init

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

for (int i = 1; i < n; i++) {

dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);

dp[i][i] = dp[i - 1][i - 1] + triangle.get(i).get(i);

}

// top down

for (int i = 1; i < n; i++) {

for (int j = 1; j < i; j++) {

dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle.get(i).get(j);

}

}

// answer --> iterate all res at last row

int min = dp[n - 1][0];

for (int i = 1; i < n; i++) {

min = Math.min(min, dp[n - 1][i]);

}

return min;

}

}