LEETCODE 1289. Minimum Falling Path Sum II 解题思路分析

题目大意:

下降路径最小和 II

给你一个整数方阵 arr ,定义「非零偏移下降路径」为:从 arr 数组中的每一行选择一个数字,且按顺序选出来的数字中,相邻数字不在原数组的同一列。

请你返回非零偏移下降路径数字和的最小值。

示例 1:

输入:arr = [[1,2,3],[4,5,6],[7,8,9]]
输出:13
解释:
 所有非零偏移下降路径包括:
 [1,5,9], [1,5,7], [1,6,7], [1,6,8],
 [2,4,8], [2,4,9], [2,6,7], [2,6,8],
 [3,4,8], [3,4,9], [3,5,7], [3,5,9]
 下降路径中数字和最小的是 [1,5,7] ,所以答案是 13 。

提示:

  • 1 <= arr.length == arr[i].length <= 200
  • -99 <= arr[i][j] <= 99

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1289

解题思路分析:

这道题最容易想到使用dfs解题。遍历每一条从上至下的路线,只要相邻两行的列不同都是合理路线,找到一条路线上数字总和最小的即是返回结果。提交后发现这样做效率不是很高,但使用java还是勉强可以通过。

看下实现代码:(后面有优化方案)

解法1:深度优先搜索dfs

Integer[][] memo; // 记忆数组
public int minFallingPathSum(int[][] arr) {
    // 初始化记忆数组
    memo=new Integer[arr.length][arr[0].length];
    // dfs递归求解
    return helper(arr,0,-1);
}
// arr是题目给定数组
// row为当前行
// col为前一行所选的列
// 返回值为当前行到末尾行间的最优解
int helper(int[][] arr, int row, int col){
    // 当前行index越界,返回0
    if(row==arr.length) return 0;
    // 记忆数组不为空,返回记忆数组中的值
    if(col!=-1&&memo[row][col]!=null) return memo[row][col];
    // 返回结果
    int res=Integer.MAX_VALUE;
    // 循环当前行每一列
    for(int i=0;i<arr[0].length;i++){
        // 如果当前列不等于前行所选的列
        if(i!=col){
            // 当前数值加上子问题的最优解为当前问题的解
            // 更新当前问题的最优解(最小值)
            // 子问题为:当前行选择第i列时,下一行到末尾行的最优解
            res=Math.min(res,helper(arr,row+1,i)+arr[row][i]);
        }
    }
    if(col!=-1){
        // 将当前问题的最优解存入记忆数组
        memo[row][col]=res;
    }
    return res;
}

本解法执行时间为109ms。

Runtime: 109 ms, faster than 6.18% of Java online submissions for Minimum Falling Path Sum II.

Memory Usage: 48.4 MB, less than 100.00% of Java online submissions for Minimum Falling Path Sum II.


解法二:

虽然普通的dfs可以勉强通过,但执行效率远远落后于题目的最优解,因此我们还需要再优化一下上面的解法。其实仔细想一想,这道题是可以使用一下贪心的,假如本题条件是相邻两行间可以使用相同列元素的话,那么最优解,一定是每一行的最小值相加而成。然而本题的难点就在于相邻两行之间是不能取同一列的元素,那么就要分成2种情况来看,

  1. 如果相邻两行的最小值在同一列上,那么我们只能用当前行的次小值与邻行最优值相加 。
  2. 如果相邻两行的最小值不在同一列上,那么我们可以用当前行的次小值与邻行最优值相加,或者当前行最小值与邻行最优值相加,两者的和最小的一方为当前最优解。

因此解法1的dfs逻辑可以按照上述情况来做出优化。在dfs递归方法中,不需要循环递归每一列,我们先找出当前行的最小值,次小值以及他们对应的列,如果最小值的列与前行选择的列相同,那么,我们只能利用本行次小值加上子问题求解。反之,如果最小值的列与前行选择的列不同,那么我们要使用当前列的最小值加上子问题,或者当前列次小值加上子问题求解,二者的最优解(最小)为当前问题的最优解。

实现代码:

    Integer[][] memo;
    public int minFallingPathSum(int[][] arr) {
        memo=new Integer[arr.length][arr[0].length];
        return helper(arr,0,-1);
    }
    
    int helper(int[][] arr, int row, int lastCol){
        if(row==arr.length) return 0;
        if(lastCol!=-1&&memo[row][lastCol]!=null){
            return memo[row][lastCol];
        }
        int res=Integer.MAX_VALUE; // 返回结果
        int min1=Integer.MAX_VALUE; // 当前行最小值
        int min1Col=0; // 最小值所在的列
        int min2=Integer.MAX_VALUE; // 次小值
        int min2Col=0; // 次小值所在的列
        // 找到最小值和次小值
        for(int i=0;i<arr[0].length;i++){
            if(arr[row][i]<=min1){
                min2=min1;
                min2Col=min1Col;
                min1=arr[row][i];
                min1Col=i;
            }else if(arr[row][i]<=min2){
                min2=arr[row][i];
                min2Col=i;
            }
        }
        // 如果最小值与前行所选的值不在同一列
        if(min1Col!=lastCol){
            // 用最小值加上子问题递归求解
            res=min1+helper(arr,row+1,min1Col);
        }
        // 用次小值加上子问题递归求解,并更新当前最优解(最小)
        res=Math.min(res,min2+helper(arr,row+1,min2Col));
        if(lastCol!=-1){
            memo[row][lastCol]=res;
        }
        return res;
    }

本解法执行时间为2ms。

Runtime: 2 ms, faster than 98.68% of Java online submissions for Minimum Falling Path Sum II.

Memory Usage: 42.4 MB, less than 100.00% of Java online submissions for Minimum Falling Path Sum II.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1289-minimum-falling-path-sum-ii-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。