本文共 1670 字，大约阅读时间需要 5 分钟。

一、动态规划

首先动态规划不是一种数据结构，而是一种优化，它是一种用空间换时间的套路，它是递归的进阶版本。

二、动态规划的套路

使用动态规划套路的一个原则是能想出递归的解法。由递归来改成动态规划。

我们以这套例题来解释动态规划的套路

第一步： 写出递归的“试”法，看看如何尝试可以解决问题。

num：表示前几步已选择的值的和， 变量

id：在下标为 0 — id-1中的数中进行选择，变量 target：程序输入的目标和，常量 arr[]： 程序输入的数组，常量

//{3,1,4,2,7}	public static boolean isSum(int[] nums, int i, int sum, int target){
   		if(i == nums.length-1)			return sum == target;		return isSum(nums, i+1, sum, target)||isSum(nums, i+1, sum+nums[i], target);//这个方法会遍历所有的子集合	}

第二步： 判断是否是无后效性问题， 什么叫后效性问题？上面这个例子，现在有一个进入isEquals（num:7，id:3）的方法，那么这个方法计算的结果，和它是通过何种方式进入的无关。比方说通过选择3和4 ， 或者选择7， 都能进入这个状态，但是一旦进入这个状态那么得到的值和前几步的选择无关。

无后效性中的变量， id num 就作为动态规划dp数组的变量。

第三步： 确定目标状态，id = 0 ， num = 0 ，是目标状态。（这里其实还比较不好理解，这是根据我们递归程序的入口定义的）

第四步： 求出终止状态和基础条件。这里也要参照我们写的递归方法

当id == arr.length时，num == target（从前n个中选，选出来的总和 == target） ，这个状态是true； 当id == arr.length，num != target，那么这些状态是false。

最后一步： 确定普遍位置由哪些精确位置得到。

递归函数中写了，DP[id][num] = DP[id+1][num] || DP[id+1][num + arr[id]]，因此这就是状态转移方程。现在进行填表即可。

从n-1行开始，DP[id][num] 需要查看DP[id+1][num] 和 DP[i+1][num + arr[id]] 这两个位置的值。 然后一步步把表填满，完成！

DP的代码不过就是把刷表的过程模拟了一遍而已。

public static boolean isSumByDP(int target,int[] arrs){
   				int sum = 0;		for(int i = 0; i < arrs.length; i++)		{
   			sum += arrs[i];		}		if(target > sum)return false;//所有值加起来都没有目标值大，直接返回false		boolean[][] dp = new boolean[arrs.length+1][sum+1];		 for (int j = 0; j <= sum; j++) {
   //先将最后一行已经知道结果的填充进去	            dp[arrs.length][j] = j==target;	        }		for(int i = arrs.length - 1; i >= 0; i--)			for(int j = 0; j <= sum; j++)			{
   				if(j + arrs[i] <= sum){
   //不超出部分,j+arrs[i]表示当前叠加值加上该位置值					dp[i][j] = dp[i+1][j] || dp[i+1][j+arrs[i]];//选中和不选中方案				}			}		return dp[0][0];	}

转载地址：http://vxrai.baihongyu.com/