Triangle

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

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

Analysis

bottom-up Dynamic programming

1. 状态: $$dp[i][j]$$: 从i,j这个点开始到最底层的最小路径和
2. 转化方程:
   $$dp[i][j]=min(dp[i+1][j],dp[i+1][j+1])+triangle[i][j]$$
   从该点开始的最小和是自己的值加上选择下面和小的那条路径
3. 初始条件: 最后一行的dp值为triangle原来的值
4. 返回值: $$dp[0][0]$$

dp for example in the question

Triangle
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
DP
[
     [11],
    [9,10],
   [7,6,10],
  [4,1,8,3]
]

Better solution:
The row dp[k+1] would be useless after dp[k] is computed, we can simply set dp as a 1D array, and iteratively update itself:
For the kth level:

$$dp[i]=min(dp[i],dp[i+1])+triangle[k][i]$$ (k from size of triangle to 0) return dp[0]

1. Get size of triangle, n
2. Initialize dp[i] to the last line of triangle
3. Update dp[i] with transfer function
4. Return dp[0]

Code

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] dp = new int[n+1];

        for (int k=n-1; k>=0; k--){
            for(int i=0; i<=k; i++){
                dp[i] = Math.min(dp[i],dp[i+1])+triangle.get(k).get(i);
            }
        }

        return dp[0];
    }
}

Reference

Ref1 Ref2