算法

(DP) $O(n^2)$

可采用自底向上的方式dp

Java 代码

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        // dp[i][j]: 从(i, j)出发min total
        // dp[i][j] = tri[i][j] + min(dp[i + 1][j], dp[i + 1][j + 1])

        int n = triangle.size();
        List<Integer> prev = triangle.get(n - 1);
        for (int i = n - 2; i >= 0; --i) {
            List<Integer> dp = new ArrayList();
            for (int j = 0; j <= i; ++j) {
                dp.add(triangle.get(i).get(j) + Math.min(prev.get(j), prev.get(j + 1)));
            }
            prev = new ArrayList(dp);
        }
        return prev.get(0);
    }
}