美文网首页
LeetCode 力扣 120. 三角形最小路径和

LeetCode 力扣 120. 三角形最小路径和

作者: windliang | 来源:发表于2020-04-10 10:19 被阅读0次

    题目描述(中等难度)

    当前层只能选择下一层相邻的两个元素走,比如第 3 层的 5 只能选择第4层的 18 ,从最上边开始,走一条路径,走到最底层最小的和是多少。

    题目解析

    先看一下 115 题 吧,和这道题思路方法是完全完全一样的。此外,119 题 倒着循环优化空间复杂度也可以看一下。

    这道题本质上就是动态规划,再本质一些就是更新一张二维表。

    115 题 已经进行了详细介绍,这里就粗略的记录了。

    解法一 递归之分治

    求第 0 层到第 n 层的和最小,就是第0层的数字加上第1层到第n层的的最小和。

    递归出口就是,第n层到第n层最小的和,就是该层的数字本身。

    public int minimumTotal(List<List<Integer>> triangle) { 
        return minimumTotalHelper(0, 0, triangle);
    }
    
    private int minimumTotalHelper(int row, int col, List<List<Integer>> triangle) {
        if (row == triangle.size()) {
            return 0;
        }
        int min = Integer.MAX_VALUE;
        List<Integer> cur = triangle.get(row);
        min = Math.min(min, cur.get(col) + minimumTotalHelper(row + 1, col, triangle));
        if (col + 1 < cur.size()) {
            min = Math.min(min, cur.get(col + 1) + minimumTotalHelper(row + 1, col + 1, triangle));
        }
        return min;
    }
    

    因为函数里边调用了两次自己,所以导致进行了很多重复的搜索,所以肯定会导致超时。

    优化的话,就是 Memoization 技术,把每次的结果存起来,进入递归前先判断当前解有没有求出来。我们可以用 HashMap 存,也可以用二维数组存。

    HashMap 的话,key 存字符串 row + "@" + col,中间之所以加一个分隔符,就是防止row = 1,col = 23row = 12, col = 3,这两种情况的混淆。

    public int minimumTotal(List<List<Integer>> triangle) {
        HashMap<String, Integer> map = new HashMap<>();
        return minimumTotalHelper(0, 0, triangle, map);
    }
    
    private int minimumTotalHelper(int row, int col, List<List<Integer>> triangle, HashMap<String, Integer> map) {
        if (row == triangle.size()) {
            return 0;
        }
        String key = row + "@" + col;
        if (map.containsKey(key)) {
            return map.get(key);
        }
        int min = Integer.MAX_VALUE;
        List<Integer> cur = triangle.get(row);
        min = Math.min(min, cur.get(col) + minimumTotalHelper(row + 1, col, triangle, map));
        if (col + 1 < cur.size()) {
            min = Math.min(min, cur.get(col + 1) + minimumTotalHelper(row + 1, col + 1, triangle, map));
        }
        map.put(key, min);
        return min;
    }
    

    动态规划

    动态规划可以自顶向下,也可以自底向上, 115 题 主要写的是自底向上,这里写个自顶向下吧。

    用一个数组 dp[row][col] 表示从顶部到当前位置,即第 row 行第 col 列,的最小和。

    状态转移方程也很好写了。

    dp[row][col] = Min(dp[row - 1][col - 1],dp[row-1][col]), triangle[row][col]

    到当前位置有两种选择,选一个较小的,然后加上当前位置的数字即可。

    public int minimumTotal(List<List<Integer>> triangle) {
        int rows = triangle.size();
        int cols = triangle.get(rows - 1).size();
        int[][] dp = new int[rows][cols];
        dp[0][0] = triangle.get(0).get(0);
        for (int row = 1; row < rows; row++) {
            List<Integer> curRow = triangle.get(row);
            int col = 0;
            dp[row][col] = dp[row - 1][col] + curRow.get(col);
            col++;
            for (; col < curRow.size() - 1; col++) {
                dp[row][col] = Math.min(dp[row - 1][col - 1], dp[row - 1][col]) + curRow.get(col);
            }
            dp[row][col] = dp[row - 1][col - 1] + curRow.get(col);
        }
        int min = Integer.MAX_VALUE;
        for (int col = 0; col < cols; col++) {
            min = Math.min(min, dp[rows - 1][col]);
        }
        return min;
    }
    

    注意的地方就是把左边界和右边界的情况单独考虑,因为到达左边界和右边界只有一个位置可选。

    接下来,注意到我们是一层一层的更新,更新当前层只需要上一层的信息,所以我们不需要二维数组,只需要一维数组就可以了。

    另外,和 119 题 题一样,更新col列的时候,会把之前col列的信息覆盖。当更新 col + 1 列的时候,旧的 col 列的信息已经没有了,所以我们可以采取倒着更新 col 的方法。

    public int minimumTotal(List<List<Integer>> triangle) {
        int rows = triangle.size();
        int cols = triangle.get(rows - 1).size();
        int[] dp = new int[cols];
        dp[0] = triangle.get(0).get(0);
        for (int row = 1; row < rows; row++) {
            List<Integer> curRow = triangle.get(row);
            int col = curRow.size() - 1;
            dp[col] = dp[col - 1] + curRow.get(col);
            col--;
            for (; col > 0; col--) {
                dp[col] = Math.min(dp[col - 1], dp[col]) + curRow.get(col);
            }
    
            dp[col] = dp[col] + curRow.get(col);
        }
        int min = Integer.MAX_VALUE;
        for (int col = 0; col < cols; col++) {
            min = Math.min(min, dp[col]);
        }
        return min;
    }
    

    另外,大家可以试一试自底向上的方法,写起来还相对简单些。

    就是 115 题 的变形了,没有新东西,如果理解了 115 题 ,那么这道题直接套算法就行,基本不用思考了。

    更多详细通俗题解详见 leetcode.wang

    相关文章

      网友评论

          本文标题:LeetCode 力扣 120. 三角形最小路径和

          本文链接:https://www.haomeiwen.com/subject/ejmlmhtx.html