算法思想之动态规划(二)——最小路径和问题

前言

我们在算法思想之动态规划(一)中讨论了动态规划的基本概念、性质和引入，如果你还没有看的话建议先去看一下。今天我们讨论一下经典的动态规划问题之最小路径和问题。

最小路径和问题

问题描述

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

问题分析

假设，一个矩阵map的行数和列数，且矩阵中从左上角出发到达第行，第列的最小路径为，则：

• 对于, 很显然，
  

• 对于第一行元素，即来说，最小路径为从矩阵左上角出发到达前一位置（第0行，第列）的最小路径 + 当前位置的权值。即,
  

• 同理，对于第一列元素，即来说，最小路径为从矩阵左上角出发到达前一位置（第0列，第行）的最小路径 + 当前位置的权值。即,
  

• 对于其他元素，即来说，最小路径为从矩阵左上角出发到达前2个位置(, )以及(, )中的较小值 + 当前位置的权值。即
  

我们要求的是。

代码实现

我们对该问题使用暴力搜索、记忆搜索和动态规划三种方法进行实现。

public class MinimumPath {
    public static HashMap<String, Integer> hashMap;

    public int getMin(int[][] map, int n, int m) {
        if (n == 0 || m == 0) {
            return 0;
        }
//        return core1(map, n, m);
//        return core2(map, n, m);
        return core3(map, n, m);
    }

    /**
     * 暴力搜素
     *
     * @param map
     * @param n
     * @param m
     * @return
     */
    public static int core1(int[][] map, int n, int m) {
        if (n == 1 && m == 1) {
            return map[n - 1][m - 1];
        }

        int res = map[n - 1][m - 1];
        if (n == 1 && m > 1) {
            res += core1(map, n, m - 1);
        } else if (n > 1 && m == 1) {
            res += core1(map, n - 1, m);
        } else if (n > 1 && m > 1) {
            res += Math.min(core1(map, n, m - 1), core1(map, n - 1, m));
        }
        return res;
    }


    /**
     * 记忆搜索
     *
     * @param map
     * @param n
     * @param m
     * @return
     */
    public static int core2(int[][] map, int n, int m) {
        if (hashMap == null) {
            hashMap = new HashMap<>();
        }

        String key = String.valueOf(n) + "_" + String.valueOf(m);
        if (n == 1 && m == 1) {
            hashMap.put(key, map[n - 1][m - 1]);
            return map[n - 1][m - 1];
        }
        if (hashMap.containsKey(key)) {
            return hashMap.get(key);
        }
        int res = map[n - 1][m - 1];
        if (n == 1 && m > 1) {
            res += core2(map, n, m - 1);
        } else if (n > 1 && m == 1) {
            res += core2(map, n - 1, m);
        } else if (n > 1 && m > 1) {
            res += Math.min(core2(map, n, m - 1), core2(map, n - 1, m));
        }
        hashMap.put(key, res);
        return res;
    }

    /**
     * 动态规划
     *
     * @param map
     * @param n
     * @param m
     * @return
     */
    public static int core3(int[][] map, int n, int m) {
        int[][] dp = new int[n][m];
        dp[0][0] = map[0][0];
        for (int i = 1; i < m; i++) {
            dp[0][i] = dp[0][i - 1] + map[0][i];
        }
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i - 1][0] + map[i][0];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + map[i][j];
            }
        }
        return dp[n - 1][m - 1];
    }

    public static void main(String[] args) {
        MinimumPath minimumPath = new MinimumPath();
        int[][] map = new int[5][4];
        map[0] = new int[]{533,385,398,226};
        map[1] = new int[]{59,529,215,203};
        map[2] = new int[]{466,262,210,597};
        map[3] = new int[]{32,359,616,194};
        map[4] = new int[]{322,485,552,493};
        int res = minimumPath.getMin(map, map.length, map[0].length);
        System.out.println(res);
    }
}

其他经典问题

• 算法思想之动态规划(三)——找零钱问题
• 算法思想之动态规划(四)——最长公共子序列问题
• 算法思想之动态规划(五)——最小编辑距离问题
• 最长上升子序列问题
• 背包问题

未来几篇博文，我将继续对经典的动态规划问题进行整理，敬请关注~
由于本人水平有限，文章难免有欠妥之处，欢迎大家多多批评指正！

写在最后

欢迎大家关注我的个人博客复旦猿。