Ming
0%

LeetCode-120

Posted on Edited on In

LeetCode-120 三角形最小路径和

题目

结果

代码

算法一：深度优先遍历二叉树（超时了）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        return goDown(triangle, 0, 0, 0, Integer.MAX_VALUE);
    }

    private int goDown(List<List<Integer>> triangle, int row, int col, int sum, Integer ans) {
        // 如果是叶子节点
        if (row == triangle.size() - 1) {
            sum += triangle.get(row).get(col);
            ans = Math.min(ans, sum);
            return ans;
        }
        int a = goDown(triangle, row + 1, col, sum + triangle.get(row).get(col), ans);
        int b = goDown(triangle, row + 1, col + 1, sum + triangle.get(row).get(col), ans);
        return Math.min(a, b);
    }
}

思路：找出从根节点到叶子节点路径和最小的那一个。

算法二：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        // 初始化
        int[][] dp = new int[triangle.size()][triangle.size()];
        dp[0][0] = triangle.get(0).get(0);

        
        for (int i = 1; i < triangle.size(); i++) {
            // 边界情况
            dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);
            int last = triangle.get(i).size() - 1;
            dp[i][last] = dp[i - 1][last - 1] + triangle.get(i).get(last);
            
            
            for (int j = 1; j < triangle.get(i).size() - 1; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle.get(i).get(j);
            }
        }
        
        // 排序后返回最小值
        Arrays.sort(dp[triangle.size() - 1]);
        return dp[triangle.size() - 1][0];
    }
}

算法三：优化动态规划

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
29
30
31
32
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        // 特殊情况
        if (triangle.size() == 1) {
            return triangle.get(0).get(0);
        }


        // 初始化
        int[][] dp = new int[2][triangle.size()];
        dp[0][0] = triangle.get(0).get(0);

        for (int i = 1; i < triangle.size(); i++) {
            // 边界情况
            dp[1][0] = dp[0][0] + triangle.get(i).get(0);
            int last = triangle.get(i).size() - 1;
            dp[1][last] = dp[0][last - 1] + triangle.get(i).get(last);


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

            // 重置dp
            System.arraycopy(dp[1], 0, dp[0], 0, dp[0].length);
        }

        // 排序后返回最小值
        Arrays.sort(dp[1]);
        return dp[1][0];
    }
}

复杂度

算法一：

时间复杂度：大于O(n²)

空间复杂度：O(n)

算法二：

时间复杂度：O(n²)

空间复杂度：O(n²)

算法三：

时间复杂度：O(n²)

空间复杂度：O(n)