LeetCode/120. 三角形最小路径和

120. 三角形最小路径和

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

相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。

例如，给定三角形：

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

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

说明：

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

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

本题若是不考虑说明中的优化空间，思路很清晰，就是动态规划。首先能想到的就是，第i个位置的路径和，与上一行相邻的元素有关，由于要求最短的路径和，所以就是在第i-1行相邻元素中选择一个最小的累加，即$dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+triangle[i][j]$，这就是状态转移方程。下面我们需要考虑一些细节，比如每行的第一个元素，它没有左邻居，所以状态转移方程为$dp[i][0]=dp[i-1][0]+triangle[i][0]$，同样要考虑的还有每行最后一个元素，它没有右邻居，所以状态转移方程为$dp[i][i]=dp[i-1][i-1]+triangle[i][i]$，最后，dp数组的最后一行就是所有路径结果和，我们只需要遍历最后一行，找出最小的值即为结果值。

具体代码如下：

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] dp = new int[n][n]; //创建一个二维数组来存放最短路径和

        dp[0][0] = triangle.get(0).get(0);  //三角形第一行只有一个元素，所以dp[0][0]就为第一行元素值

        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);   //每行第一个元素只与上一个第一个元素有关
            dp[i][i] = dp[i - 1][i - 1] + triangle.get(i).get(i);   //每行最后一个元素只与斜对角线上的上一行元素有关
            for (int j = 1; j < i; j++) {
                //普通位置元素与上一行j-1和j的元素值有关
                dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle.get(i).get(j);
            }
        }

        //结果数组的最后一行存放着各个情况的路径和，只需要遍历找出最小的即可
        int result = dp[n - 1][0];
        for (int i = 0; i < n; i++) {
            result = Math.min(result, dp[n - 1][i]);
        }

        return result;
    }
}

当然，这种做法空间复杂度都比较惨烈，我们来思考一下空间还有没有更进一步优化的空间。

通常，动态规划优化空间复杂度都是去除存储的无关值，在本题中，可以看到dp[i][j]只与上一层的dp[i-1][j-1]和dp[i-1][j]有关，所以我们只需要记录这些值即可，具体的思想这里参考了官方题解。要想优化到O(n)的空间复杂度，就需要使用一维数组存储结果。从 i 到0递减地枚举j，这样我们只需要一个长度为n的一维数组f，就可以完成状态转移，即$dp[j]=min(dp[j-1],dp[j])+triangle[i][j]$

具体代码如下：

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] dp = new int[n]; //创建一个二维数组来存放最短路径和

        dp[0] = triangle.get(0).get(0);  //三角形第一行只有一个元素，所以dp[0][0]就为第一行元素值

        for (int i = 1; i < n; i++) {
            //这里由于使用逆序遍历，所以三条语句的顺序不能打乱，不然会使得结果出错
            dp[i] = dp[i - 1] + triangle.get(i).get(i);

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

        int result = dp[0];
        for (int i = 1; i < n; i++) {
            result = Math.min(result, dp[i]);
        }

        return result;
    }
}