算法初级-07-动态规划系列

作者: 囧么肥事 | 来源:发表于2019-07-23 09:43 被阅读0次

年轻即出发...

简书：https://www.jianshu.com/u/7110a2ba6f9e

知乎：https://www.zhihu.com/people/zqtao23/posts

GitHub源码：https://github.com/zqtao2332

个人网站：http://www.zqtaotao.cn/ （停止维护更新内容，转移简书）

QQ交流群：606939954

咆哮怪兽一枚...嗷嗷嗷...趁你现在还有时间，尽你自己最大的努力。努力做成你最想做的那件事，成为你最想成为的那种人，过着你最想过的那种生活。也许我们始终都只是一个小人物，但这并不妨碍我们选择用什么样的方式活下去，这个世界永远比你想的要更精彩。

最后：喜欢编程，对生活充满激情

本节内容预告

介绍递归和动态规划

实例1：n!

实例2：汉诺塔问题

实例3：字符串子序列

实例4：母牛生育问题

实例5：最小路径和

实例6：金额问题

介绍递归和动态规划

暴力递归：

1，把问题转化为规模缩小了的同类问题的子问题

2，有明确的不需要继续进行递归的条件(base case)

3，有当得到了子问题的结果之后的决策过程

4，不记录每一个子问题的解

动态规划

1，从暴力递归中来

2，将每一个子问题的解记录下来，避免重复计算

3，把暴力递归的过程，抽象成了状态表达

4，并且存在化简状态表达，使其更加简洁的可能

暴力递归就是暴力尝试！

动态规划是用来优化暴力尝试的！

今天的内容就是暴力递归到动态规划的转化。

实例1

为了理解尝试

求n!的结果

见到此题，脑海第一反应for

// for
    public static long getFactorialByFor(int n){
        long res = 1L;
        for (int i = 1; i < n; i++) {
            res *= i;
        }
        return res;
    }

递归版本

要想解决 n! 问题，需要解决子问题（n-1)! ，然后 n * (n-1)!就是求得的解。

要想解决（n-1)! 问题，需要解决子问题（n-2)! ，然后（n-1)! * (n-2)!就是求得的解。

要想解决（n-2)! 问题，需要解决子问题（n-3)! ，然后（n-2)! * (n-3)!就是求得的解。

....

递归实质就是将问题转化为一个个同等类型的子问题

// recur
public static long getFactorialByRecur(int n) {
    if(n == 1) return 1;
    return (long) n * getFactorialByRecur(n - 1);
}

实例2

为了理解尝试

汉诺塔问题
打印n层汉诺塔从最左边移动到最右边的全部过程

对于N层汉诺塔，递归求解

如图3层模拟N层

第一步需要将 N-1 层的汉诺塔从from移动到help上

第二步将第N层的汉诺塔从from移动到to上

将from当做help，help当做from，继续前两步操作

第三步需要将 N-2 层的汉诺塔从from移动到to上

第四部将第N-1层的汉诺塔从from移动到to上

...

递归以上行为

图解以上行为

3层汉诺塔

2_1_汉诺塔.png

第一步需要将 N-1 层的汉诺塔从from移动到help上

第二步将第N层的汉诺塔从from移动到to上

2_2_汉诺塔.png

将from当做help，help当做from，继续前两步操作

2_3_汉诺塔.png

第三步需要将 N-2 层的汉诺塔从from移动到to上

第四部将第N-1层的汉诺塔从from移动到to上

2_4_汉诺塔.png

具体实现

    /**
     *
     * @param N 表示 这是 1 到 N的问题 1：N
     * @param from N 层汉诺塔原柱子
     * @param to N 层汉诺塔移动的目标柱子
     * @param help 辅助移动柱子
     *
     * 第一步需要将 N-1 层的汉诺塔从from移动到help上
     * 第二步将第N层的汉诺塔从from移动到to上
     *
     * 将from当做help，help当做from，继续前两步操作
     * 第三步需要将 N-2 层的汉诺塔从from移动到to上
     * 第四部将第N-1层的汉诺塔从from移动到to上
     *
     * 递归以上行为
     */
    public static void process(int N, String from, String to, String help){ // N问题 从 from 到 to ，借助help
        if (N == 1){ // 表示 前N - 1 个已经从from移动到了help上, 是1到N的问题
            System.out.println("move " + N + " from " + from + " to " + to);
        } else { // 否则是 1 到N-1 层问题
            process(N - 1, from, help, to); // N - 1 问题 从from 到 help， 借助to
            System.out.println("move " + N + " from " + from + " to " + to);
            process(N - 1, help, to, from); // 挪回来, 从help 到to， 借助from

            /*
                T(N) = T(N-1)+1+T(N-1)
                N-1 个移动到辅助柱子
                N移动到目标柱子
                N-1 挪回来
             */
        }
    }

实例3

为了理解尝试

打印一个字符串的全部子序列，包括空字符串

3_1_穷举.png

    /**
     * @param chars 字符数组
     * @param i 当前字符下标
     * @param pre 上一个递归，给定的结果
     */
    public static void printAllSubString(char[] chars, int i, String pre){
        if (i == chars.length) {
            // 字符数组中每一个字符已经选择完毕
            System.out.println(pre);
            return;
        }

        printAllSubString(chars, i + 1, pre + chars[i]); // 选择要当前字符
        printAllSubString(chars, i + 1, pre + "_"); // 选择不要当前字符
    }

实例4

牛生育问题

母牛每年生一只母牛，新出生的母牛成长三年后也能每年生一只母牛，假设不会死。求N年后，母牛的数量。

4_1_枚举牛生育.png

第5年的牛=第4年的牛+新生牛（新生牛由可以生育的牛生产=第2年的牛）

同理

第6年的牛=第5年的牛+新生牛（第3年的牛都可以生育=第3年的牛）

4_2_牛出生规律.png

实例5

最小的路径和

给你一个二维数组，二维数组中的每个数都是正数，要求从左上角走到右下角，每一步只能向右或者向下。沿途经过的数字要累加起来。返回最小的路径和。

暴力尝试

4 9 0 2

7 9 4 1

8 0 8 1

6 4 3 4

从4 开始走，向右向下，两条路，

向右最短路径和：4 9 0 2 1 1 4

向下最短路径和：4 7 8 0 4 3 4

所以最短路径和：4 9 0 2 1 1 4

注意：这里有一个思维盲区，最短路径和，不是每次选取最小的下一步走，而是，选取直达目标的的这一路的路径和最短的。

public static int  minPath(int[][] matrix){
        if (matrix == null || matrix.length == 0) return 0;
        return work(matrix, 0, 0);
    }

    // 从(r,c)点到右下角位置最短路径和
    public static int work(int[][] matrix, int r, int c) {
        if (r == matrix.length - 1 && c == matrix[0].length - 1) { // 当前点到达右下角位置
            return matrix[r][c];// 从右下角位置到右下角位置，路径和等于右下角值
        }

        if (r == matrix.length - 1 && c != matrix[0].length - 1) { // 到达最后一行
            return matrix[r][c] + work(matrix, r, c + 1); // 只能向右移动
        }

        if (r != matrix.length - 1 && c == matrix[0].length - 1) { // 到达最后一列
            return matrix[r][c] + work(matrix, r + 1, c);
        }

        // 既可以向右，也可以向下
        int right = work(matrix, r, c + 1); // right -> 右边位置到最右下角的最短路径和
        int down = work(matrix, r + 1, c); // down -> 下边位置到最右下角的最短路径和
        return matrix[r][c] + Math.min(right, down);



        // 暴力尝试
        // 暴力尝试存在的问题
        // 多次的重复计算
    }

暴力尝试存在的问题：多次的重复计算，导致非常耗费时间。

记忆化搜索，使用一个map将已经计算过的保存下来，等需要使用的时候直接通过key-value取，可以节省很多时间.

什么情况下的递归可以改成动态规划?

递归展开有重复状态，而且重复状态与到达的路径是没有关系的（无后效性问题），那么一定是可以改成动态规划的。

整个动态规划的套路，不管你是一维，二维，三维数组。注意，以下都是和暴力尝试是反过来的。

1、把需要的位置点出来

2、回到base case中，把不被依赖的位置设置好

3、分析一个普遍位置是怎么依赖的，看需要哪些状态。推出普遍状态之后，整个暴力尝试的计算顺序就可以知道了，反过来就是整个动态规划的计算顺序。

以此题为例

1、把需要的位置点出来，对于此题就是左上角位置(0,0)

2、回到base case中，把不被依赖的位置设置好，对于此题就是最后一行，最后一列值。但是递归改为动态规划是反的，所以是第一行和第一列

3、分析一个普遍位置是怎么依赖的，看需要哪些状态。对于此题，看母函数调用了哪些子函数

(r,c) --> (r,c+1) (r+1,c) ,

对于此题就是一个普遍位置，需要的是右边状态和下边状态。

推出普遍状态之后，整个暴力尝试的计算顺序就可以知道了，反过来就是整个计算顺序。

PS：动态规划，先写出尝试版本，暴力尝试。写出尝试版本后，分析可变参数，哪几个可变参数可以代表返回值的状态，可变参数是几维的，dp就是一张几维表

查看动态规划做此题的一些状态转移

原矩阵

-------开始打印-------
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0
-------结束打印-------

第一步：添加标记目标位置（暴力尝试目标的反位置）

-------开始打印-------
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
-------结束打印-------

第二步：查看base case，设置好不被依赖的点

行

-------开始打印-------
1 4 9 18
0 0 0 0
0 0 0 0
0 0 0 0
-------结束打印-------

列

-------开始打印-------
1 4 9 18
9 0 0 0
14 0 0 0
22 0 0 0
-------结束打印-------

第三步：普遍位置：比较右和上，选最小

右 = 当前 + 上

下 = 当前 + 左

-------开始打印-------
1 4 9 18
9 5 8 12
14 0 0 0
22 0 0 0
-------结束打印-------

-------开始打印-------
1 4 9 18
9 5 8 12
14 5 11 12
22 0 0 0
-------结束打印-------

-------开始打印-------
1 4 9 18
9 5 8 12
14 5 11 12
22 13 15 12
-------结束打印-------

import cn.zqtao.learn.model.MatrixModel;

public class Code_45_2_dp_MinPath {

    public static int minPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
            return 0;
        }

        MatrixModel.printMatrix(matrix);// 打印原矩阵

        int rowSize = matrix.length;
        int colSize = matrix[0].length;

        int[][] dp = new int[rowSize][colSize];

        dp[0][0] = matrix[0][0]; // 第一步，标记目标位置。对于此题就是左上角位置(0,0)

        MatrixModel.printMatrix(dp); // 打印第一步状态


        // 第二步、回到base case中，把不被依赖的位置设置好，对于此题就是最后一行，最后一列值,
        // 但是递归改为动态规划是反的，所以是第一行和第一列
        for (int c = 1; c < colSize; c++) { // 第一行
            dp[0][c] = matrix[0][c] + dp[0][c - 1];
        }
        MatrixModel.printMatrix(dp);

        for (int r = 1; r < rowSize; r++) { // 第一列
            dp[r][0] = matrix[r][0] + dp[r - 1][0];
        }
        MatrixModel.printMatrix(dp);

        for (int r = 1; r < rowSize; r++) {
            for (int c = 1; c < colSize; c++) {
                int right = matrix[r][c] + dp[r - 1][c]; // 右状态
                int down = matrix[r][c] + dp[r][c - 1]; // 下状态
                dp[r][c] = Math.min(right, down);
            }
            MatrixModel.printMatrix(dp);
        }

        return dp[rowSize - 1][colSize - 1];
    }

    public static void main(String[] args) {
        int[][] m = { { 1, 3, 5, 9 }, { 8, 1, 3, 4 }, { 5, 0, 6, 1 }, { 8, 8, 4, 0 } };
        System.out.println(minPath(m));
    }
}

矩阵模型

/**
 * @description:随机生成矩阵，打印矩阵等
 * @version: 1.0
 */
public class MatrixModel {

    // random matrix 随机产生 rowSize 行，colSize列的矩阵
    public static int[][] generateRandomMatrix(int rowSize, int colSize) {
        if (rowSize < 0 || colSize < 0) return null;

        int[][] m = new int[rowSize][colSize];
        for (int i = 0; i < rowSize; i++) {
            for (int j = 0; j < colSize; j++) {
                m[i][j] = (int) (Math.random() * 10);
            }
        }
        return m;
    }

    // print matrix
    public static void printMatrix(int[][] matrix) {
        System.out.println("-------开始打印-------");
        if (matrix == null || matrix.length == 0) return;

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                System.out.print(matrix[i][j] + "\t");
            }
            System.out.println();
        }
        System.out.println("-------结束打印-------");
    }
}

实例6

给你一个数组arr，和一个整数aim。如果可以任意选择arr中的数字，能不能累加得到aim，返回true或者false

暴力尝试

    /**
     * @param arr
     * @param i 当前位置下标
     * @param sum 当前总数
     * @param aim 目标数
     * @return 是否能凑齐
     */
    public static boolean isSum(int[] arr, int i, int sum, int aim){
        if (i == arr.length) { // 表示已经到达最后位置
            return sum == aim;
        }

        if (sum == aim) {
            return true;
        }

        // 加上当前值，和不加上当前值，任意一个满足即可
        return isSum(arr, i + 1, sum, aim) || isSum(arr, i + 1, sum + arr[i], aim);
    }

动态规划

    public static boolean isSum(int[] arr, int aim) {
        boolean[][] dp = new boolean[arr.length + 1][aim + 1];

        printMatrix(dp);
        for (int i = 0; i < dp.length; i++) {
            dp[i][aim] = true;
        }
        printMatrix(dp);

        for (int i = arr.length - 1; i >= 0; i--) { // 0 --> arr.length -1    arr
            for (int j = aim - 1; j >= 0 ; j--) { // 0 -->  aim-1  目标额
                if (j + arr[i] <= aim) { // 如果 j + 当前数，小于aim，
                    // dp[i][j] = 加上当前值，和不加上当前值，任意一个满足即可
                    dp[i][j] = dp[i + 1][j] || dp[i + 1][j + arr[i]];
                }
            }
        }
        printMatrix(dp);

        return dp[0][0];
    }

    // print matrix
    public static void printMatrix(boolean[][] matrix) {
        System.out.println("-------开始打印-------");
        if (matrix == null || matrix.length == 0) return;

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                System.out.print(matrix[i][j] + "\t");
            }
            System.out.println();
        }
        System.out.println("-------结束打印-------");
    }

状态转移

    public static void main(String[] args) {
        int[] arr = { 1, 3, 4 };
        int aim = 7;
        System.out.println(isSum(arr, aim));
    }




-------开始打印-------
false   false   false   false   false   false   false   false   
false   false   false   false   false   false   false   false   
false   false   false   false   false   false   false   false   
false   false   false   false   false   false   false   false   
-------结束打印-------
-------开始打印-------
false   false   false   false   false   false   false   true    
false   false   false   false   false   false   false   true    
false   false   false   false   false   false   false   true    
false   false   false   false   false   false   false   true    
-------结束打印-------
-------开始打印-------
true    false   true    true    true    false   true    true    
true    false   false   true    true    false   false   true    
false   false   false   true    false   false   false   true    
false   false   false   false   false   false   false   true    
-------结束打印-------
true

算法初级-07-动态规划系列

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

囧囧算法