[数据结构与算法]算法设计与分析 动态规划

思路

1 题目 ——> 尝试方法 ——> 暴力递归 —(可变参数)—> 记忆化搜索（dp） ——> 严格表结构（dp）
2 暴力递归到记忆化搜索，增加dp表结构，记录递归的结果，减少重复递归的计算
3 严格表结构，在记忆化搜索的dp表结果上，通过递归函数找到dp表结构内部之间的依赖关系，在不使用递归的情况下，只通过表的内部关系将dp表补充完整，找到答案对应dp表中的结果
4 严格表结构的求解顺序：（1）可变参数的确定（2）终止位置的确定（3）根据basecase确定不用计算的位置（4）观察依赖，推理内部普遍位置（5）确定依次推理的顺序
5 注意在暴力递归时每个 if 语句都是有 return 结尾的，所以都是 if 可以没有 else if 。但是在改写成动态规划后一定要确定是 if 还是 else if
6 关键点：可变参数的确定，可变参数的范围，数目是评价尝试方法的重要指标

题目一：机器人走K步到达M点问题

假设有排成一行的N个位置，记为1~N，N一定大于或等于2;
开始时机器人在M（1 <= M <= N）位置上，
如果机器人位于1位置，那么下一步只能走到2位置，
如果机器人位于N位置，那么下一步只能走到N-1位置，
如果机器人位于中间的任一位子，那么下一步可以向左走，也可以向右走。
机器人必须走K步，最终来到P（1 <= P <= N），给定参数N，M，K，P，有多少种走法？

暴力递归

• 尝试方法：运动分为向左或向右两种情况，尝试所有的移动可能，步数走完到达结束位置就算成功

    public static int walkWays(int N, int M, int K, int P){
        return process(N, P, K, M);
    }

    public static int process(int N, int end, int rest, int cur){
        //N固定参数：开始格子的大小
        //end固定参数：结束位置
        //rest可变参数：剩余的步数
        //cur可变参数：目前的位置
        if (rest == 0){
            //步数用完，停在结束位置，本次尝试正确
            //basecase
            return cur == end ? 1 : 0;
        }
        if (cur == 1){
            //1位置，下一步只能走到2
            return process(N, end, rest - 1, 2);
        }
        if (cur == N){
            //N位置，下一步只能走到N - 1;
            return process(N, end, rest - 1, N - 1);
        }
        return process(N, end, rest - 1, cur - 1) + process(N, end, rest - 1, cur + 1);
    }

时间复杂度：整个决策可以看成一颗二叉树，高度就是步数k，则为，O(2 ^ k)

记忆化搜索dp

• 从暴力递归到记忆化搜索dp
  （1）若 1，2，3，4，5 从2开始到4结束，步数为4，N为5
  （2）N，end为固定参数每次调用都相同省去，rest与cur留下
  （3）暴力递归，将所有的结构都列出来，下图中：f(2，2）得到的结果一定是相同的，但是在暴力递归中会重复计算
  （4）思路：利用空间记录相同的计算结果，减少计算次数，实现记忆化搜索
  
• 增加记录相同计算过程的缓存结构：dp
• 每次将结构记录到dp中，相同的计算不再进行递归

    public static int walkWays(int N, int M, int K, int P){
        //记忆化搜索
        //由可变参数的范围和数量，确定dp的规模
        //rest的范围 0 ~ K，cur的访问 1 ~ N，dp二维表
        int[][] dp = new int[K + 1][N + 1];
        for (int i = 0; i < dp.length; i++){
            for (int j = 0; j < dp[0].length; j++){
            	//dp数组中的默认值为0 
                //将dp中所有位置的值改为负一
                dp[i][j] = -1;
            }
        }
        return process(N, P, K, M, dp);
    }

    public static int process(int N, int end, int rest, int cur, int[][] dp){
        //N固定参数：开始格子的大小
        //end固定参数：结束位置
        //rest可变参数：剩余的步数
        //cur可变参数：目前的位置
        //增加dp参数
        if (dp[rest][cur] != -1){
            //dp[][]不为负一，说明已经进行过计算，不用再次递归
            return dp[rest][cur];
        }
        //返回之前，都在dp[][]中记录
        if (rest == 0){
            //步数用完，停在结束位置，本次尝试正确
            //basecase
            dp[rest][cur] = cur == end ? 1 : 0;
            return dp[rest][cur];
        }
        if (cur == 1){
            //1位置，下一步只能走到2
            dp[rest][cur] = process(N, end, rest - 1, 2, dp);
        } else if (cur == N){
            //N位置，下一步只能走到N - 1;
            dp[rest][cur] = process(N, end, rest - 1, N - 1, dp);
        } else {
            dp[rest][cur] = process(N, end, rest - 1, cur - 1, dp) + process(N, end, rest - 1, cur + 1, dp);
        }
        return dp[rest][cur];
    }

时间复杂度：因为，递归每次都在填dp的表，且重复，所以时间复杂度由dp的规模决定，O(K * N)，
K步数，N格子的个数

严格表结构dp

• 记忆化搜索dp到严格表结构dp
  （1）若 1，2，3，4，5 从2开始到4结束，步数为4，N为5
  （2）由rest与cur得到dp表，* 号位置代表最终返回位置
  
  （3）由basecase得到，rest = 0，只有cur = 2时为 1，其余均为 0，并且cur != 0
  
  （4）通过递归函数找依赖关系：cur = 1，依赖右上角（则：cur = 1 ， rest = 1时其值与cur = 2 ，rest = 0时相同为0）cur = N，依赖左上角，其余cur，依赖左上角 + 右上角，每行开始依次补充完整dp表
  
  （5）顺序：从左到右，从上到下

    public static int walkWays(int N, int M, int K, int P){
        //严格表结构
        //由可变参数的范围和数量，确定dp的规模
        //rest的范围 0 ~ K，cur的访问 1 ~ N，dp二维表
        //dp[K][M]答案的位置，步数K，初始位置M
        //dp[0][P]初始值为1的位置，步数为0，结束位置为要求位置
        int[][] dp = new int[K + 1][N + 1];
        dp[0][P] = 1;
        for (int i = 1; i < dp.length; i++){
            //按照行的顺序依次补充表结构
            //cur为1的位置，其值依赖于其右上角
            dp[i][1] = dp[i - 1][2];
            for (int j = 2; j < dp[0].length - 1; j++){
                //其余位置依赖于左上角 + 右上角
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
            }
            //cur为N的位置，其值依赖于其左上角
            dp[i][N] = dp[i - 1][N - 1];
        }
        return dp[K][M];
    }

题目二：零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

暴力递归

• 尝试方法：从左先右，每个硬币分为要或不要，尝试所有可能，硬币遍历结束后达到总金额就算成功

    public static int minCoint(int[] coins, int amout){
        //使用较少的硬币
        //构造成功返回硬币个数
        //构造失败返回 -1
        return process(coins, amout, 0);
    }

    public static int process(int[] coins, int rest, int index){
        //index目前遍历到硬币数组的位置
        //rest目前还要达到的金额
        if (rest < 0){
            //出现负数，构成失败
            return -1;
        }
        if (rest == 0){
            //构造成功
            return 0;
        }
        //rest > 0
        if (index == coins.length){
            //rest > 0时，coins数组已经用完，构造失败
            return -1;
        }
        //p1不要index位置的硬币
        int p1 = process(coins, rest, index + 1);
        //p2要index位置的硬币
        int p2 = process(coins, rest - coins[index], index + 1);
        if (p1 == -1 && p2 == -1){
            //要和不要都失败
            return -1;
        } else {
            if (p1 == -1){
                //不要失败，选择要，硬币数加一
                return p2 + 1;
            }
            if (p2 == -1){
                //要失败，选择不要
                return p1;
            }
            //要不要都可以，选择使用总硬币数少的
            return Math.min(p1, p2 + 1);
        }
    }

记忆化搜索dp

• 增加记录缓存结构dp
• 使用变化参数rest，index建立dp表

    public static int minCoint(int[] coins, int amout){
        //使用较少的硬币
        //构造成功返回硬币个数
        //构造失败返回 -1
        int[][] dp = new int[amout + 1][coins.length + 1];
        for (int i = 0; i < dp.length; i++){
            for (int j = 0; j < dp[0].length; j++){
                //因为-1，在此题中有含义，故将初始值设置为-2
                dp[i][j] = -2;
            }
        }
        return process(coins, amout, 0, dp);
    }

    public static int process(int[] coins, int rest, int index, int[][] dp){
    	//动态规划
        //index目前遍历到硬币数组的位置
        //rest目前还要达到的金额
        if (rest < 0){
            //二维数组中rest不能为负数，所以放在最开始位置
            return -1;
        }
        if (dp[rest][index] != -2){
            return dp[rest][index];
        }
        if (rest == 0){
            //构造成功
            dp[rest][index] = 0;
        } else if (index == coins.length){
            //rest > 0时，coins数组已经用完，构造失败
            dp[rest][index] = -1;
        } else {
            //p1不要index位置的硬币
            int p1 = process(coins, rest, index + 1, dp);
            //p2要index位置的硬币
            int p2 = process(coins, rest - coins[index], index + 1, dp);
            if (p1 == -1 && p2 == -1){
                //要和不要都失败
                dp[rest][index] = -1;
            } else {
                if (p1 == -1){
                    //不要失败，选择要，硬币数加一
                    dp[rest][index] = p2 + 1;
                }else if (p2 == -1){
                //要失败，选择不要
                    dp[rest][index] = p1;
                }else {
                    //要不要都可以，选择使用总硬币数少的
                    dp[rest][index] = Math.min(p1, p2 + 1);
                }
            }
        }
        return dp[rest][index];
    }

严格表结构dp

• 若coins为 [2，3，5，1] , amount为6
  （1）根据递归函数初始化，rest = 0，值为0，index = 4，值为 -1，求（0，6）的位置，即初始化设置 rest = 0，其值为0，初始化设置 index = coins.length，其值为 -1
  
  （2）内部的点由上一个点的（rest, index + 1）与（rest - coins[index], index + 1）共同决定
  （3）整体填表的顺序由 index 从 coins.length - 1 到 0，rest 从 1 到 amount + 1
  （4）结过在dp[ amount ][ 0 ]

    public static int minCoint(int[] coins, int amount) {
        //严格表结构
        int[][] dp = new int[amount + 1][coins.length + 1];
        for (int col = 0; col < coins.length + 1; col++) {
            //初始化设置 rest = 0，其值为0
            dp[0][col] = 0;
        }
        for (int row = 1; row < amount + 1; row++) {
            //初始化设置 index = coins.length，其值为 -1
            dp[row][coins.length] = -1;
        }
        for (int index = coins.length - 1; index >= 0; index--) {
            for (int rest = 1; rest < amount + 1; rest++) {
                //内部剩余点的设置
                //将递归改为给dp表填值
                //p1不要index位置的硬币
                int p1 = dp[rest][index + 1];
                //p2要index位置的硬币
                int p2 = -1;
                if (rest - coins[index] >= 0){
                    p2 = dp[rest - coins[index]][index + 1];
                }
                if (p1 == -1 && p2 == -1) {
                    //要和不要都失败
                    dp[rest][index] = -1;
                } else {
                    if (p1 == -1) {
                        //不要失败，选择要，硬币数加一
                        dp[rest][index] =  p2 + 1;
                    }else if (p2 == -1) {
                        //要失败，选择不要
                        dp[rest][index] =  p1;
                    }else {
                        //要不要都可以，选择使用总硬币数少的
                        dp[rest][index] =  Math.min(p1, p2 + 1);
                    }
                }
            }
        }
        //返回指定位置的值
        return dp[amount][0];
    }

题目三：拿纸牌比最大问题

暴力递归

• 思路：
  （1）分为两种拿牌方式，先手和后手，若范围为left ~ right
  （2）先手分为左右，若拿left，值就是就是left位置的值 + 后手的值(left + 1 ~ right后手)；若拿right，值就是right位置的值 + 后手的值(left ~ right - 1后手)，返回二者值中较大的
  （3）后手分为对手拿左还是右，若对手拿left，值就是先手的值(left + 1 ~ right先手)；若拿right，值就是先手的值(left ~ right - 1先手)，因为对手一定拿最优解，那么后手一定是二者值中较小的情况
  （4）若 left == right 先手就是 left位置的值，后手就是0

    public static int win(int[] arr){
        if (arr == null || arr.length == 0){
            return 0;
        }
        int valueA = first(arr, 0, arr.length - 1); //A的先手情况
        int valueB = second(arr, 0, arr.length - 1); //B的后手情况
        return Math.max(valueA, valueB);
    }

    public static int first(int[] arr, int left, int right){
        //先手获得的最好分数
        if (left == right){
            //递归结束条件
            return arr[left];
        }
        int l = arr[left] + second(arr, left + 1, right); //拿左边
        int r = arr[right] + second(arr, left, right - 1); //拿右边
        return Math.max(l, r);
    }

    public static int second(int[] arr, int left, int right){
        //先手获得的最好分数
        if (left == right){
            //递归结束条件
            return 0;
        }
        int l = first(arr, left + 1, right); //对手拿走了左边
        int r = first(arr, left, right - 1); //对手拿走了右边
        //因为对手一定会挑选最优情况，所以留给后手一定是俩者中较差的选择
        return Math.min(l, r);
    }

记忆化搜索dp

• 有两个递归函数，构建两个dp表进行记录

    public static int win(int[] arr){
        if (arr == null || arr.length == 0){
            return 0;
        }
        int[][] dpF = new int[arr.length][arr.length];
        int[][] dpS = new int[arr.length][arr.length];
        for (int i = 0; i < dpF.length; i++){
            for (int j = 0; j < dpF[0].length; j++){
                //初始化，为填入时全为 -1
                dpF[i][j] = -1;
                dpS[i][j] = -1;
            }
        }
        int valueA = first(arr, 0, arr.length - 1, dpF, dpS); //A的先手情况
        int valueB = second(arr, 0, arr.length - 1, dpF, dpS); //B的后手情况
        return Math.max(valueA, valueB);
    }

    public static int first(int[] arr, int left, int right, int[][] dpF, int[][] dpS){
        //先手获得的最好分数
        //在first递归函数中加入 dpF缓存
        if (dpF[left][right] != - 1){
            return dpF[left][right];
        }
        if (left == right){
            //递归结束条件
            dpF[left][right] = arr[left];
        } else {
            int l = arr[left] + second(arr, left + 1, right, dpF, dpS); //拿左边
            int r = arr[right] + second(arr, left, right - 1, dpF, dpS); //拿右边
            dpF[left][right] = Math.max(l, r);
        }
        return dpF[left][right];
    }

    public static int second(int[] arr, int left, int right, int[][] dpF, int[][] dpS){
        //先手获得的最好分数
        //在second递归函数中加入 dpS缓存
        if (dpS[left][right] != - 1){
            return dpS[left][right];
        }
        if (left == right){
            //递归结束条件
            dpS[left][right]  = 0;
        } else {
            int l = first(arr, left + 1, right, dpF, dpS); //对手拿走了左边
            int r = first(arr, left, right - 1, dpF, dpS); //对手拿走了右边
            dpS[left][right] = Math.min(l, r);
        }
        //因为对手一定会挑选最优情况，所以留给后手一定是俩者中较差的选择
        return dpS[left][right];
    }

严格表结构

例：arr[] = [3，100，4，50]
（1）first dp表与 second dp表中 因为 left 始终在 right 左侧 所以都只有上半侧，* 号为目标位置

（2）初始化当 left == right：first 中为 arr[ left ]，second 中为 0

（3）普遍位置的依赖关系：first 与 second 分别互相依赖；例：first(0, 3) 由 second(1, 3) 与 second(0, 2)共同决定

（4）次序：依次求对角线，整体从上往下，从左往右，最终位置 [0][arr.length - 1]

    public static int win(int[] arr){
        if (arr == null || arr.length == 0){
            return 0;
        }
        int[][] dpF = new int[arr.length][arr.length];
        int[][] dpS = new int[arr.length][arr.length];
        for (int i = 0; i < dpF.length; i++){
            //初始化
            dpF[i][i] = arr[i];
            dpS[i][i] = 0;
        }
        for (int n = 1; n < arr.length; n++){
            //斜对角线的添加
            int col = n;
            for (int row = 0; row < arr.length - n; row++){
                dpF[row][col] = Math.max(arr[col] + dpS[row][col - 1], arr[row] + dpS[row + 1][col]);
                dpS[row][col] = Math.min(dpF[row][col - 1], dpF[row + 1][col]);
                col++;
            }
        }
        return Math.max(dpF[0][arr.length - 1], dpS[0][arr.length - 1]);
    }

题目四：象棋问题（三维动态规划）

• 问题描述：
  给你一个棋盘，长为10，宽为9，然后在棋盘的[0,0]位置，有一个马，马走日嘛，就是象棋的规则，现在在棋盘上给你一个位置[a,b]，给你k步，请你求出，马走到【a，b】位置并且走k步，可以有多少种走法？

暴力递归

• 尝试方法：所有马可能的落点进行尝试，可以改写成从[a, b] 到 [0, 0]用k步，basecase为 k = 0

    public static int getWays(int a, int b, int k){
        return process(a, b, k);
    }

    public static int process(int x, int y, int step){
        //x，y目前位置的坐标
        //step还剩的步数
        if (x < 0 || x > 8 || y < 0 || y > 9){
            //出界情况
            return 0;
        }
        if (step == 0){
            //basecase
            return x == 0 && y == 0 ? 1 : 0;
        }
        return process(x - 1, y + 2, step - 1)
                + process(x + 1, y + 2, step - 1)
                + process(x - 1, y - 2, step - 1)
                + process(x + 1, y - 2, step - 1)
                + process(x - 2, y + 1, step - 1)
                + process(x + 2, y + 1, step - 1)
                + process(x - 2, y - 1, step - 1)
                + process(x + 2, y - 1, step - 1);
    }

记忆化搜索dp

• 三维表结构记录

    public static int getWays(int a, int b, int k){
        int[][][] dp = new int[9][10][k + 1];
        for (int x = 0; x < dp.length; x++){
            for (int y = 0; y < dp[0].length; y++){
                for (int z = 0; z < dp[0][0].length; z++){
                    dp[x][y][z] = -1;
                }
            }
        }
        return process(a, b, k, dp);
    }

    public static int process(int x, int y, int step, int[][][] dp){
        //x，y目前位置的坐标
        //step还剩的步数
        if (x < 0 || x > 8 || y < 0 || y > 9){
            //出界情况
            return 0;
        }
        if (dp[x][y][step] != - 1){
            return dp[x][y][step];
        }
        if (step == 0){
            //basecase
            dp[x][y][step] = x == 0 && y == 0 ? 1 : 0;
        } else{
            dp[x][y][step] = process(x - 1, y + 2, step - 1, dp)
                    + process(x + 1, y + 2, step - 1, dp)
                    + process(x - 1, y - 2, step - 1, dp)
                    + process(x + 1, y - 2, step - 1, dp)
                    + process(x - 2, y + 1, step - 1, dp)
                    + process(x + 2, y + 1, step - 1, dp)
                    + process(x - 2, y - 1, step - 1, dp)
                    + process(x + 2, y - 1, step - 1, dp);
        }
        return dp[x][y][step];
    }

严格表结构dp

（1）初始化：最底层（0，0，0）位置是1，其余（x，y，0）位置均为0
（2）每一次都根据其下一层得到
（3）一层一层填写，x，y的顺序不影响，最终位置为（x，y，step）

        public static int getWays(int x, int y, int step){
            if (x < 0 || x > 8 || y < 0 || y > 9 || step < 0){
                //出界情况
                return 0;
            }
            int[][][] dp = new int[9][10][step + 1];
            //初始化
            dp[0][0][0] = 1;
            for (int z = 1; z < dp[0][0].length; z ++){
                //一次一次的填充
                for (int i = 0; i < dp.length; i++){
                    for (int j = 0; j < dp[0].length; j++){
                        dp[i][j][z] += process(i - 1, j + 2, z - 1, dp);
                        dp[i][j][z] += process(i + 1, j + 2, z - 1, dp);
                        dp[i][j][z] += process(i - 1, j - 2, z - 1, dp);
                        dp[i][j][z] += process(i + 1, j - 2, z - 1, dp);
                        dp[i][j][z] += process(i - 2, j + 1, z - 1, dp);
                        dp[i][j][z] += process(i + 2, j + 1, z - 1, dp);
                        dp[i][j][z] += process(i - 2, j - 1, z - 1, dp);
                        dp[i][j][z] += process(i + 2, j - 1, z - 1, dp);
                    }
                }
            }
            return dp[x][y][step];
        }

        public static int process(int x, int y, int step, int[][][] dp){
            //防止越界
            if (x < 0 || x > 8 || y < 0 || y > 9){
                //出界情况
                return 0;
            }
            return dp[x][y][step];
        }