笔试算法模拟题精解之“矩阵最小路径和”

原文链接

题目名称

矩阵最小路径和

题目地址

https://developer.aliyun.com/coding/34

题目描述

概述：

给定一个矩阵，大小为m，从左上角开始每次只能向右走或者向下走，最后达到右下角的位置。路径中所有数字累加起来就是路径和，返回所有路径的最小路径和。

示例1

比如输入矩阵为

4 1 5 3
3 2 7 7
6 5 2 8
8 9 4 5           

最小路径为：

23           

方法一

动态规划思想：先求简单值在逐步递推求复杂值，后面的值通过前面的结果来求得。

保证每一步的最小值进行存储即可

思路：

新建一个矩阵dp（大小也是M*M），该矩阵是从上往下，从左往右记录每一步的结果的，当前的结果可以根据该矩阵上面和左边最小的值来获得。

public class Top34 {  

    public int solution(int[][] m) {  
        if(m==null){  
            return 0;  
        }  
        if(m.length==0){  
            return 0;  
        }  
        int[][] dp = new int[m.length][m[0].length];  

        dp[0][0] = m[0][0];  
        //先计算第一行  
        for (int i = 1; i < m.length; i++) {  
            dp[i][0] = dp[i-1][0]+m[i][0];  
        }  
        //计算第一列  
        for (int i = 1; i < m[0].length; i++) {  
            dp[0][i] = dp[0][i-1]+m[0][i];  
        }  

        //从上->下，左->右 计算当前位置的最小值  
        for (int i = 1; i < m.length; i++) {  

            for (int j = 1; j < m[0].length; j++) {  
                dp[i][j] = Math.min(dp[i][j-1],dp[i-1][j]) + m[i][j];  
            }  

        }  

        return dp[m.length-1][m[0].length-1];  
    }  
}             

时间复杂度O(M

*

M)，空间复杂度O(M

*

M)

消耗

执行用时：7ms

执行内存：9kb

动态规划求解问题的特点：

• 从暴力递归中来
• 把每一个子问题的解记录下来，避免重复计算
• 把暴力递归的过程，抽象成了状态表达
• 并且存在化简状态表达，使其更加简洁

方法二

暴力求解。

public class Top34_2 {  

    public int solution(int[][] m) {  
        if(m==null){  
            return 0;  
        }  
        if(m.length==0){  
            return 0;  
        }  
        return minPath(m,0,0);  
    }  


    /**  
     * 暴力递归方式求解最短路径问题  
     * @param array 二维数组  
     * @param i  当前走到的行  
     * @param j  当前走到的列  
     * @return  
     */  
    private static int minPath(int[][] array, int i, int j){  
        //当i的值为array.length - 1并且j的值为array[0].length  - 1时表示走到了右下角  
        if(i == array.length - 1 && j == array[0].length  - 1){  
            //走到了右下角则直接返回右下角的数值  
            return array[i][j];  
        }  

        //当i的值为array.length - 1并且j的值不为array[0].length - 1时，只能往右走  
        if(i == array.length - 1 && j != array[0].length - 1){  
            return array[i][j] + minPath(array, i ,j + 1);  
        }else if(i != array.length - 1 && j == array[0].length - 1){  
            //当i的值不为array.length - 1并且j的值为array[0].length - 1时，只能往下走  
            return array[i][j] + minPath(array, i + 1, j);  
        }  

        //否则既可以向下走也可以向右走，此时选取路径最短的那个  
        return array[i][j] + Math.min(minPath(array, i, j + 1), minPath(array, i + 1, j));  
    }  
}             

时间复杂度O(2^M)

执行内存：6kb

暴力递归求解问题的特点：

• 把问题转化为规模缩小了的同类问题的子问题
• 有明确的不需要继续进行递归的条件
• 有当得到了子问题的结果之后的决策过程
• 不记录每一个子问题的解

与汝俱进。

作者 | 谙忆