题解 | #三角形最小路径和# [P0]

从下往上dp

f(i,j) = Min{f(i+1,j), f(i+1,j+1)} + v(i,j)
O(n^2), O(n^2)
TODO: 第二个for-loop倒着走可以空间优化至O(n)

import java.util.*;

public class Solution {
    public int minTrace (int[][] triangle) {
       int len = triangle.length;
       if (len == 0) return 0;

       // f(i,j)=Min{f(i+1,j), f(i+1,j+1)} + val(i, j)
       int[][] dp = new int[len][len];
       for (int i = len-1; i >= 0; i--) {
         for (int j = 0; j <= i; j++) {
           if (i == len-1) {
             dp[i][j] = triangle[i][j];
           } else {
             dp[i][j] = Math.min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j];
           }
         }
       }
       return dp[0][0];
    }
}