题目描述

给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如,给定三角形:

[
      [2],
     [3,4],
    [6,5,7],
   [4,1,8,3]
]

自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。

说明:

如果你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题,那么你的算法会很加分。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/triangle
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解法1

这道题目使用dp来求解,通过之前求得小规模的问题计算更大规模的问题。题目提到“每一步只能移动到下一行中相邻的结点上”,我们把题目给定的样例按照最左端对其,我们将这个数组记为triangle

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]

我们在triangle数组中找一个比较general的case,对于元素8,它的上一行只有5和7能够走到8。也就是说当元素处于第i行第j列时(i,j从0计数),只能从i-1, j-1与i-1, j的位置走来。我们就可以定义数组dp[i][j]表示自顶向下走到第i, j位置时最小路径和,有dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]

需要注意一点的是越界处理。当i=0,j=0时,自顶向下只有triangle[0][0]一个元素,取dp[i][j] = trangle[i][j];当j=0时,dp[i-1][j-1]是越界的,取dp[i][j] = dp[i-1][j] + triangle[i][j];当j=i时,dp[i-1][j]是越界的,取dp[i][j] = dp[i-1][j-1] + triangle[i][j]

在实现时,我们采用Bottom-up的解法,声明与triangle数组同型(大小一致)的数组dp,递增变量i,j,将变量带入公式循环更新dp数组,最终的答案为min(dp[dp.length - 1])。在实现中,为了避免扫描dp[dp.length – 1]来求最小值,我们使用临时变量来存储当前遇到的最小值。

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int[][] dp = new int[triangle.size()][];
        int ans = 0;

        for (int i = 0; i < triangle.size(); i++) {
            dp[i] = new int[triangle.get(i).size()];
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < triangle.get(i).size(); j++) {
                if (i == 0 && j == 0)
                    dp[i][j] = triangle.get(i).get(j);
                else if (j == 0)
                    dp[i][j] = dp[i - 1][j] + triangle.get(i).get(j);
                else if (j == i)
                    dp[i][j] = dp[i - 1][j - 1] + triangle.get(i).get(j);
                else
                    dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle.get(i).get(j);
                min = Math.min(min, dp[i][j]);
            }
            ans = min;
        }

        return ans;
    }
}

解法1优化

题目提到“如果你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题,那么你的算法会很加分。”,下面我们就来优化解法1的空间复杂度。通过观察dp公式,可以看出dp[i][j]仅依赖于dp[i-1][j-1]与dp[i-1][j]。那我们可以声明大小为dp[2][|triangle|]的数组,循环使用dp[0]与dp[1]。dp[0]表示上一轮计算结果,dp[1]表示本轮计算结果,当完成一轮迭代后交换dp[0]与dp[1]。

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int[][] dp = new int[2][triangle.get(triangle.size() - 1).size()];
        int ans = 0;

        for (int i = 0; i < triangle.size(); i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < triangle.get(i).size(); j++) {
                if (i == 0 && j == 0)
                    dp[1][j] = triangle.get(i).get(j);
                else if (j == 0)
                    dp[1][j] = dp[0][j] + triangle.get(i).get(j);
                else if (j == i)
                    dp[1][j] = dp[0][j - 1] + triangle.get(i).get(j);
                else
                    dp[1][j] = Math.min(dp[0][j - 1], dp[0][j]) + triangle.get(i).get(j);
                min = Math.min(min, dp[1][j]);
            }
            ans = min;
            int[] tmp = dp[0];
            dp[0] = dp[1];
            dp[1] = tmp;
        }

        return ans;
    }
}
pwrliang Algorithms, Dynamic Programming ,

Leave a Reply

Your email address will not be published. Required fields are marked *