120. Triangle

,

DFS(TLE)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    private static class SumHolder {
        private int sum = Integer.MAX_VALUE;
    }

    public int minimumTotal(List<List<Integer>> triangle) {
        SumHolder sumHolder = new SumHolder();
        dfs(triangle, 0, 0, 0, sumHolder);
        return sumHolder.sum;
    }

    private void dfs(List<List<Integer>> triangle, int levelIndex, int index, int sum, SumHolder sumHolder) {
        if (levelIndex == triangle.size()) {
            sumHolder.sum = Math.min(sumHolder.sum, sum);
            return;
        }

        dfs(triangle, levelIndex + 1, index, sum + triangle.get(levelIndex).get(index), sumHolder);
        dfs(triangle, levelIndex + 1, index + 1, sum + triangle.get(levelIndex).get(index), sumHolder);
    }
}

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        // 定义 dp[i][j] 为以 triangle.get(i).get(j) 结尾的最小路径和
        int[][] dp = new int[n][n];
        dp[0][0] = triangle.get(0).get(0);

        for (int i = 1; i < n; i++) {
            // 注意左右两个端点需要特殊处理

            // 左端点没有左上角元素
            dp[i][0] = triangle.get(i).get(0) + dp[i - 1][0];
            // 右端点没有上侧元素
            dp[i][i] = triangle.get(i).get(i) + dp[i - 1][i - 1];

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

        int minSum = dp[n - 1][0];
        for (int sum : dp[n - 1]) {
            minSum = Math.min(minSum, sum);
        }

        return minSum;
    }
}

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        List<Integer> dp = triangle.get(triangle.size() - 1);
        for (int i = triangle.size() - 2; i >= 0; i--) {
            // 从下层中选取小的元素值进行累加
            for (int j = 0; j <= i; j++) {
                dp.set(j, Math.min(dp.get(j), dp.get(j + 1)) + triangle.get(i).get(j));
            }
        }

        return dp.get(0);
    }
}

References

120. Triangle
剑指 Offer II 100. 三角形中最小路径之和