【算法】【递归与动态规划模块】矩阵的最小路径和

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
给定一个矩阵，在矩阵中只能往右或者往下走，每走到一个格子，路径会增加格子所表示的数值，问从左上角到右下角的最短路径是多少？
如:
[ 1 3 5 9 8 1 3 4 5 0 6 1 8 8 4 0 ]

⎣ ⎡​1858​3108​5364​9410​⎦ ⎤​
从左上角1开始到右下角0的最短路径为1,3,1,0,6,1,0 和为12

解决方案

原问题：
方法一：暴力递归
1、从终点开始看，能到0的只能是1和4，所以到0的最短路径距离就是 0 + Math.min(到4的最短距离，到1的最短距离)
方法二：动态规划
1、通过表达式：min[i][j] = Math.min(min[i-1][j], min[i][j-1])
2、初始化min矩阵的第一行和第一列，累加和
3、每一个元素都通过上面的状态转换表达式计算出来即可
方法三：动态规划降低空间维度版本
方法2中的矩阵为二维矩阵，而方法3只需要一个一维矩阵，新值和旧值滚动更新即可，具体可以查看代码

代码编写

java语言版本

递归方法：

    /**
     * 递归方法
     * @param arr
     * @return
     */
    public static int minPath(int[][] arr) {
        if (arr == null || arr.length == 0 || arr[0].length == 0) {
             return 0;
        }
        return process(arr, arr.length - 1, arr[0].length - 1);
    }

    /**
     * 递归主体
     * 返回到达arr[i][j] 的最小距离
     * @param arr
     * @param i 横坐标
     * @param j 纵坐标
     */
    private static int process(int[][] arr, int i, int j) {
        if (i == 0 && j == 0) {
            return arr[i][j];
        }else if (i == 0) {
            return arr[i][j] + process(arr, i, j-1);
        }else if (j == 0) {
            return arr[i][j] + process(arr, i-1 , j);
        }else {
            // 找到前面或者上面较小的那个
            return arr[i][j] + Math.min(process(arr, i-1, j), process(arr, i, j-1));
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

标准动态规划：

   /**
     * 动态规划最小路径
     * @param arr
     * @return
     */
    public static int minPathForDP(int[][] arr) {
        if (arr == null || arr.length == 0 || arr[0].length == 0) {
            return 0;
        }
        // 动态规划矩阵dp[i][j]代表到arr[i][j]的最短路径和
        int[][] dp = new int[arr.length][arr[0].length];
        dp[0][0] = arr[0][0];
        for (int i = 1; i < arr.length; i++) {
            dp[0][i] = dp[0][i-1] + arr[0][i];
        }
        for (int j = 1; j < arr[0].length; j++) {
            dp[j][0] = dp[j-1][0] + arr[j][0];
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j < arr[0].length; j++) {
                dp[i][j] = arr[i][j] + Math.min(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[arr.length-1][arr.length-1];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

动态规划（节省空间版本）:

    /**
     * 动态规划最小路径
     * 空间降低一个维度
     * @param arr
     * @return
     */
    public static int minPathForDPReduceMem(int[][] arr) {
        if (arr == null || arr.length == 0 || arr[0].length == 0) {
            return 0;
        }
        int[] dp = new int[arr.length];
        dp[0] = arr[0][0];
        for (int i = 1; i < arr.length; i++) {
            dp[i] = dp[i-1] + arr[0][i];
        }
        for (int i = 1; i < arr.length; i++) {
            dp[0] += arr[i][0];
            for (int j = 1; j < arr.length; j++) {
                dp[j] = arr[i][j] + Math.min(dp[j-1], dp[j]);
            }
        }
        return dp[arr.length-1];
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

1、这道题是一道明显的基础dp动态规划问题，通过这道题的三种方法可以感觉到如上篇斐波那契数列文章所述，这些题目有一个共同点就是结果依赖于上一个或多个状态，只要有递推关系，那么就可以很快的列出递归方法。
2、dp我个人感觉是递归的一种升级版本，递归中存在重复计算，比如到达[i][j]的最短距离需要计算[i-1][j] ,而 到达[i-1][j+1]的地方同样需要再次计算到达[i][j]的最短距离，并且只要经过i,j的所有路径都会重新一次i,j,所以递归叫做暴力递归，确实很暴力并且浪费很多计算资源，其根本原因是重复计算的值没有被保存下来，所以dp帮助递归做了一个计算结果的保存，dp可以保证每一个节点只计算一次，这样将性能大大提升了。
3、那么有个疑问，递归是否能够被dp所代替？我觉得应该不能，从二叉树类型问题就可以体现出来。那么什么样的递归才可以被dp所代替？
其实仔细分析递归过程可以发现，当前这道题的递归过程特别像二叉树，但是递归其实可以变成多叉树，取决于当前状态依赖于几个前状态。那么回来想一下可以发现这道题的递归过程分解成二叉树后，其实有很多分叉是重复的，也就是重复计算的地方，当出现这种情况的递归时，说明递归时可以优化的，但是二叉树中每一个节点都是不同的对象，所以二叉树的问题是不可以使用dp优化的，只有递归过程存在重复计算的，计算过的可以保存起来作为缓存，下次计算前查一下缓存即可，那么dp其实就是一个kv键值对的缓存，k就是i，j，v就是dp[i][j].到这里应该就解答了疑问了。

写在最后

方案和代码仅提供学习和思考使用，切勿随意滥用！如有错误和不合理的地方，务必批评指正~
如果需要git源码可邮件给2260755767@qq.com
再次感谢左大神对我算法的指点迷津！