数据结构与算法之暴力递归改动态规划

不念不忘少年蓝@ 2021-12-15 05:59 317阅读 0赞

# 数据结构与算法之暴力递归改动态规划 #

--------------------

## 目录 ##

1.  二维数组最小路径和
2.  暴力递归改动态规划解析
3.  任意选择数组arr中的数字，看能不能累加得到aim

--------------------

### 1. 二维数组最小路径和 ###

###### （一） 题目描述 ######

![在这里插入图片描述][20190704151650246.png]

###### （二） 思路 ######

1.  递归版
    
    1.  如果 i == matrix.length && j == matrix\[0\].length，说明到了右下角，返回即可。
    2.  如果 i == matrix.length - 1，说明到了最后一行，只能向右走
    3.  如果 j == matrix\[0\].length - 1，说明到了最后一列，只能向下走
    4.  获取向右走和向下走的最短路径和。
    5.  取向右走和向下走中小的一个加入当前点即为最短路径和。（每一步都是如此）

//递归版
        public static int walk(int[][] matrix, int i, int j) {
        
            if (i == matrix.length && j == matrix[0].length) {
        
                return matrix[i][j];
            }
            if (i == matrix.length - 1) {
        
                return matrix[i][j] + walk(matrix, i, j + 1);
            }
            if (j == matrix[0].length - 1) {
        
                return matrix[i][j] + walk(matrix, i + 1, j);
            }
            //right -》 右边位置到右下角的最短路径和
            int right = walk(matrix, i, j + 1);
            //down -》 下边位置到右下角的最短路径和
            int down = walk(matrix, i + 1, j);
            return matrix[i][j] + Math.min(right, down);
        }

--------------------

### 2. 暴力递归改动态规划解析 ###

1.  什么样的尝试版本可以改动态规划？
    
    1.  当递归过程中发现有重复状态，而且重复状态与到达的路径是没有关系的，那么一定可以改动态规划
    2.  就是说，(0,0)到（1,1)，不管(0,0)是向右走再向下走,还是向下走再向右走到达（1,1）（1,1）的最短路径还是不会变，叫无后效性问题。参数固定了，返回值一定是固定的，就是无后效性问题。  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]  
        ![在这里插入图片描述][20190704162621109.png]
2.  因为 i，j的变化范围我们知道，是一张二维表。所以所有的返回值肯定都在这个表里面。也就是说，可以在一张表中
    
    1.  把需要的位置点出来
    2.  回到base case中，把不被依赖的值设置好
    3.  回到递归中，发现假设当前点是（i，j），一个普遍的位置需要右边的状态和下边的状态
    4.  推出普遍位置依赖之后，反过去就是计算顺序，最后一行弄好，从右到左，从下到上依次推到顶部就是答案。这就是暴力递归改动态规划的统一套路
    5.  如上个题：  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 1]
3.  总的就是说
    
    1.  写出尝试版本
    2.  分析可变参数，分析哪几个参数可以代表返回值状态，可变参数是几维的，它就是几维表
    3.  看看最终的状态是哪一个，在表中点出来，然后回到base case中，把不依赖的值设置好，看看一个普遍位置需要哪些位置，逆着回去，就是填表的顺序，这就是暴力递归改动态规划
4.  上述题由暴力递归改动态规划代码实现为

public static int minPath1(int[][] matrix) {
        
            return process1(matrix, matrix.length - 1, matrix[0].length - 1);
        }
    
        public static int process1(int[][] matrix, int i, int j) {
        
            int res = matrix[i][j];
            if (i == 0 && j == 0) {
        
                return res;
            }
            if (i == 0 && j != 0) {
        
                return res + process1(matrix, i, j - 1);
            }
            if (i != 0 && j == 0) {
        
                return res + process1(matrix, i - 1, j);
            }
            return res + Math.min(process1(matrix, i, j - 1), process1(matrix, i - 1, j));
        }
    
        public static int minPath2(int[][] m) {
        
            if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
        
                return 0;
            }
            int row = m.length;
            int col = m[0].length;
            int[][] dp = new int[row][col];
            dp[0][0] = m[0][0];
            for (int i = 1; i < row; i++) {
        
                dp[i][0] = dp[i - 1][0] + m[i][0];
            }
            for (int j = 1; j < col; j++) {
        
                dp[0][j] = dp[0][j - 1] + m[0][j];
            }
            for (int i = 1; i < row; i++) {
        
                for (int j = 1; j < col; j++) {
        
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + m[i][j];
                }
            }
            return dp[row - 1][col - 1];
        }

--------------------

### 3. 任意选择数组arr中的数字，看能不能累加得到aim ###

1.  题目描述  
    ![在这里插入图片描述][20190704165254622.png]
2.  代码实现

public class Code_08_Money_Problem {
        
    
    	public static boolean money1(int[] arr, int aim) {
        
    		return process1(arr, 0, 0, aim);
    	}
    
    	public static boolean process1(int[] arr, int i, int sum, int aim) {
        
    		if (sum == aim) {
        
    			return true;
    		}
    		// sum != aim
    		if (i == arr.length) {
        
    			return false;
    		}
    		return process1(arr, i + 1, sum, aim) || process1(arr, i + 1, sum + arr[i], aim);
    	}
    
    	public static boolean money2(int[] arr, int aim) {
        
    		boolean[][] dp = new boolean[arr.length + 1][aim + 1];
    		for (int i = 0; i < dp.length; i++) {
        
    			dp[i][aim] = true;
    		}
    		for (int i = arr.length - 1; i >= 0; i--) {
        
    			for (int j = aim - 1; j >= 0; j--) {
        
    				dp[i][j] = dp[i + 1][j];
    				if (j + arr[i] <= aim) {
        
    					dp[i][j] = dp[i][j] || dp[i + 1][j + arr[i]];
    				}
    			}
    		}
    		return dp[0][0];
    	}
    
    	public static void main(String[] args) {
        
    		int[] arr = {
         1, 4, 8 };
    		int aim = 12;
    		System.out.println(money1(arr, aim));
    		System.out.println(money2(arr, aim));
    	}
    
    }

[20190704151650246.png]: /images/20211214/2b95e2c258a04ff6a84cc972b92603e2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]: /images/20211214/7cc1c41314464ab38db60b01e469cf2e.png
[20190704162621109.png]: /images/20211214/b7f7c09146844d75928f9165e9b36d0f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 1]: /images/20211214/a8b1b1d767e64f759edeac0fb00569b5.png
[20190704165254622.png]: /images/20211214/e1bc0795791c4c36b4ba04553739ce58.png