前言：

之前只是听说过暴力递归和动态规划这些个名词。写这篇文章的目的只是想总结总结自己的认识。

暴力递归

其实也不用叫什么暴力递归，感觉加上暴力这个词就有一种不正经的感觉…
就是一个简单的递归尝试方法。 出现了一个问题，不知道是怎么解决的，但我们知道可以怎么一步一步进行尝试，在这一步步的尝试过程就可以把问题解决了。
相信大家第一次接触递归的方法都是从 斐波那契的那些兔子开始的~
最具典型性的例子应该就是 四色定理。 一个人为的证明很难，但被电子计算机（注意是电子哦~不是机械）一次次的尝试，花了1200个小时证明出来的定理。

动态规划

其本质就是一种 空间换时间 的操作。
是从递归的写法改过来的。有些递归发放是会大量重复计算相同的值，也就是执行相同的步骤。把这些 东西抽象出来，就有了动态规划这种方法。
也就是说，动态规划是由递归方法改过来的，但不是所有可以写成递归方法的问题都可以改成动态规划。

以下看看2到题目来加深印象…

• 第一题： 矩阵的最小路径和

题目：

思路：

因为只能往右走或者往下走。从左上角到右下角。
首先看第一个位置，要决定往下走还是往右走，取决于是下面那条路到目的地的和最小 还是 右面那条路到目的地的和最小。这里可以分别算出往下走的路的和 与 往右走的路的和，在进行选择。
好了，假设选好了前面的那一条路（选了往下走也好还是往右走也罢，先不管这些，反正是选好了），接下来因为还没到达目的地，剩下的选择还是往下走还是往右走，只是区别是这次的路不一样了，规模更小了，较之前问题这次的矩阵规模更小了。
这样一次次的尝试之后，知道到达目的地为止。
所以这是一种采用递归方法解决问题的途径。但是要注意此时的边界问题： 到了最后一列，只能选择往下走；到了最后一行，只能选择往右走。

• 这种思路的代码实现：

// matrix : 代表这整个矩阵 ； i : 此时走到了 第i行； j ： 此时走到了 第j列 
   public static int minPath(int[][] matrix, int i, int j) {
   
   	// 3个if处理边界情况
   	// 到达了最右下角，返回此时的值
   	if(i == matrix.length-1 && j == matrix[0].length-1) {
   
   		return matrix[i][j];
   	}
   	
   	// 到达了最后一行，此时只能往右走 放回此时位置的值 加上 往右走的最小路径和
   	if(i == matrix.length-1) {
   
   		return matrix[i][j] + matrix[i][j+1];
   	}
   	
   	// 到达了最后一列，此时只能往下走。 放回此时位置的值 加上 往下走的最小路径和
   	if(j == matrix[0].length-1) {
   
   		return matrix[i][j] + matrix[i+1][j];
   	}
   	
   	// 普通情况， 最小和 是 此时位置的值， 加上 往右走 或者 往下走 的最小路径和
   	return matrix[i][j] + Math.min(minPath(matrix, i+1, j), minPath(matrix, i, j+1));
   }

优化：

因为之前的方法有时候已经算过了某个路径的最小值，可是后面用到了还是要在重新算一遍。 存在着这样的大量的重复计算工作。
所以就想一种方法把之前算过的值保存起来，以后再用到的时候，直接拿起来用就可以了。 自然而然的，就生成与原矩阵一样大的一块二维表（因为是动态规划方法，所以取名dp表…），表上的位置存储 相应的位置 到达最右下角的最小路径和。对于此题，我们想要的就是这块二维表的最左上角的位置的信息。
好了，这种优化的方式就是我所理解的动态规划方法，一种空间换时间的操作。

• 这种优化的代码实现 ：

public static int minPathDp(int[][] matrix) {
   
		// 生成一张与原矩阵同样大的二维dp表
		int row = matrix.length;
		int col = matrix[0].length;
		int[][] dp = new int[row][col];
		
		// 填上 右下角的信息
		dp[row-1][col-1] = matrix[row-1][col-1];
		
		// 填上 最后一列 的信息
		for(int r = row-2; r >= 0; r--) {
   
			dp[r][col-1] = matrix[r][col-1] + dp[r+1][col-1];
		}
		
		// 填上 最后一行 的信息
		for(int c = col-2; c >= 0; c--) {
   
			dp[row-1][c] = matrix[row-1][c] + dp[row-1][c+1];
		}
		
		// 填上 剩下的空表格
		for(int r = row-2; r >= 0; r--) {
   
			for(int c = col-2; c >= 0; c--) {
   
				dp[r][c] = matrix[r][c] + Math.min(dp[r][c+1], dp[r+1][c]);
			}
		}
		
		return dp[0][0];
	}

尽管如此，动态规划的方法还有 可以 压缩空间的优化。具体的实现目前还不是很清楚…

• 第二题 ：

题目 ：

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

思路 ：

从arr中的数字一个一个的看，每一位数字都可以要，也可以不要，记录此时选择的数字情况所累加得到的和。直到每种情况都看完了，也就是到了数字的最后一位数字了，看看此时的累加和 是否等于 aim，返回相应的true或false。

• 这种思路的代码实现：

// arr : 这个数组 ； sum ： 来到i位置时，所累加得到的和； i ： 此时来到数组的 第i个 位置； aim ： 目标数字
	public static boolean isSum(int[] arr, int sum, int i, int aim) {
   
		// 当整个数组的数字全都看完了的时候
		if(i == arr.length-1) {
   
			return sum == aim;
		}
		
		// 选择不要 第i个位置 的数字； 就来到了第i+1个位置， 累加和还是之前的和
		boolean b1 = isSum(arr, sum, i+1, aim); 
		
		// 选择要 第i个位置 的数字； 就来到了第i+1个位置， 累加和 是 之前的累加和 再加上 选择要第i个位置上的数字 之后形成的和 
		boolean b2 = isSum(arr, sum+arr[i], i+1, aim);
		
		// 不管是 选择哪一种情况， 只要一个是true， 就放回true
		return b1 || b2;
	}

动态规划的方法

可以说算是动态规划的方法吧…
就是根据递归的写法直接改成动态规划的方法：
在递归写法中，找出可变参数， 再找出依赖项，再找出这个dp表中我们想要的是哪一块。 找出不需要依赖其他项的，先填，也就是先填递归到底的情况和边界情况。
对于这题来说，可变参数是 i 和 sum。 所以生成i行， sum列dp表。i代表：这个数组一共有几个数字，这个表就有几行（一共有0到N行（N是有N个数字））。 sum代表，这个数组的所有数字全部加起来所形成的和。aim比sum小 才可能放回true，也才对我们有意义。
一开始不需要依赖的是最后一行，也就是将所有数字累加起来，只有累加和形成了aim的那块才是true，其余都是false。 之后填剩下的空。对于此题，依赖的是（sum，i+1）和（sum+arr[i]，i+1）。

• 上代码

public static boolean isSumDp(int[] arr, int aim) {
   
		int i = arr.length+1;
		int sum = 0;
		for(int j = 0; j < arr.length; j++) {
   
			sum += arr[j];
		}
		
		if(aim > sum) {
   
			return false;
		}
		
		boolean[][] dp = new boolean[i][sum+1];   // 开列边界的时候，在aim左边有可能在加上当前数会超过sum从而越界。
												  // 比如数组2， 3， 5； aim为7时。sum为10，但aim左边有个6+arr[2]（就是5这个数字） = 11越界
		// 底下全部一行 赋值为 false， 后面会改第aim列的为true
		for(int c = 0; c <= sum; c++) {
   
			 dp[i-1][c] = false;
		}
		for(int r = i-1; r >= 0; r--) {
   
			dp[r][aim] = true;
		}
		// 第aim列之后的全为false
		for(int r = 0; r <= i-1; r++) {
   
			for(int c = aim+1; c <= sum; c++) {
   
				dp[r][c] = false;
			}
		}
		
		// 填dp表 中剩下的依赖项
		for(int r = i-2; r >= 0; r--) {
   
			for(int c = 0; c < aim; c++) {
   
				if( c + arr[r] > sum) {
   		// 如果超出越界的话，肯定是false了（在aim之后的列自然都是false）。 所以只有看前面一个条件就好了
					dp[r][c] = dp[r+1][c] ; 
				} else {
   
					dp[r][c] = dp[r+1][c] || dp[r+1][ c+arr[r] ];
				}
			}
		}
		
		return dp[0][0]; 
	}