関小君刷题记

题目大意：

下降路径最小和 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-解题思路分析/