动态规划算法的理解算法

动态规划（dynamic programming）与分治方法类似，都是通过组合子问题的解来求解原问题。但是动态规划算法对每个子子问题只求解一次，将其保存在一个表格中，从而无需每次求解一个子子问题时都重复计算，避免来这种不必要对对计算工作。
通常按照一下四个步骤来设计一个动态规划算法：

刻画一个最优对结构特征。
递归地定义最优解对值。
计算最优解的值，通常采用自底向上的方法。
利用计算出的信息构造一个最优解。

动态规划算法通常基于一个递推公式及一个或多个初始状态。当前子问题的解将由上一次子问题的解推出。首先，需要先找到某个状态的最优解，然后在它的帮助下，找到下一状态的最优解，“状态”用来描述该问题的子问题的解。“状态”并不是随便给的，在大多数情况下，某个状态只与它前面出现的状态有关，而独立于后面的状态。然后分析状态转移方程以及初始状态。

动态规划的本质就是递归，这样比较容易判断一个问题是否可以用动态规划算法去求解，因为只要思考问题的规模缩小/扩大之后是不是同样的方法求解即可。

适用应用动态规划算法求解的最优问题应该具备两个要素：

最优子结构
子问题重叠

如果一个问题的最优解包含其子问题的最优解，则称此问题具有最优解结构的性质。
重叠子问题其实就是子问题空间必须足够“小”，即问题的递归算法会反复的求解相同的子问题，而不是一直生成新的子问题。

下面，我们来看一个动态规划经典的问题：求最长递增序列长度LIS（longest increasing subsequence）

设有由n个不相同的整数组成的数列，记为:a(1)、a(2)、……、a(n)且a(i)<>a(j) (i<>j)
若存在i1

问题：一个序列有n个数：a[1],a[2],…,a[N]，求出最长非降子序列的长度
首先，我们先理一下思路：
1）我们最终目标是要求n个数的序列中最长非降子序列的长度，如果能先求出a[1]，a[2]，a[i](i 2）为了简化理解如何找到状态转移方程的，我们可以让i=1,2,3,4,5。如果我们要求的这n个数的序列是：

18，7，14，20，18，23

根据前面的状态，我们可以进行推断：
（1）i=1时，序列：18，LIS长度d(1)=1;
（2）i=2时，序列：7，此时7前面没有比7小的了，所以LIS长度d(2)=1;
（3）i=3时，序列：7,14，此时14前面有7比它小，所以LIS长度d(3)=2也可以理解为d(3)=d(2)+1;
（4）i=4时，序列：7，14，20，此时20前面7，14比它小，有LIS长度d(4)=3，即d(4)=d(3)+1;
分析到这里，我们基本上可以找到状态转移的方程了，如果我们已经求出了d(1)到d(i-1)，那么d(i)可以用下面的状态转移方程得到：

d(i) = max{1, d(j) + 1}，其中要满足条件：j < i && a[j] <= a[i]

程序如下：

public static void getLongest(int[] arr, int n){ //存放状态 int[] d = new int[n]; //最长非降子序列长度初始化为1 int length = 1; //状态初始化为1 d[0] = 1; for (int i = 1; i < n; i++){ //状态初始化为1 d[i] = 1; for (int j = 0; j < i; j++){ if (arr[i] > arr[j] && d[j] + 1 > d[i]){ d[i] = d[j] + 1; } if (length < d[i]){ length = d[i]; } } }System.out.println(length); }

上面line11-line18即内层for循环其实就是我们在求a[1]，a[2]，a[i](i 上面的时间复杂度为n^2，下面我们通过二分法将时间复杂度降为nlogn，代码如下：

public class Test {public static void main(String[] args) { Scanner scanner = new Scanner(System.in); System.out.println("请输入序列："); String[] strLines = scanner.nextLine().trim().split(" "); int n = strLines.length; int[] nums = new int[n + 1]; int[] f = new int[n + 1]; for (int i = 1; i <= n; i++){ nums[i] = Integer.parseInt(strLines[i-1]); f[i] = Integer.MAX_VALUE; } scanner.close(); f[1] = nums[1]; //通过记录f数组的有效位数，求得个数 int len = 1; for (int i = 2; i <= n; i++){ int l = 0; int r = len; int mid; //若大于末尾，则向后填充 if (nums[i] > f[len]){ f[len++] = nums[i]; } else { //二分法查找将时间复杂度降为nlogn while (l < r){ mid = l + (r-l)/2; if (f[mid] > nums[i]){ r = mid; } else { l = mid + 1; } } f[l] = Math.min(nums[i], f[l]); } } System.out.println(len); } }

在这我们在继续求解另外一个关于序列的问题，两个序列中的最长公共子序列（ LCS ）
譬如给定2个序列：

1 2 3 4 5
3 2 1 4 5

试求出最长的公共子序列。
显然长度是 3 ，包含 345三个元素（不唯一）
解析：
可以用 dp[i][j] 来表示第一个串的前 i 位，第二个串的前j位的 LCS的长度，那么我们是很容易想到状态转移方程的：
如果当前的 nums1[i] 和 nums2[j] 相同（即是有新的公共元素）那么dp[ i ] [ j ] = max(dp[ i ] [ j ], dp[ i-1 ] [ j-1 ] + 1);
如果不相同，即无法更新公共元素，考虑继承：dp[i][j]=max(dp[i?1][j],dp[i][j?1])
代码如下：

public class Test {public static void main(String[] args) { Scanner scanner = new Scanner(System.in); System.out.println("请输入序列1："); String[] str1 = scanner.nextLine().trim().split(" "); int n = str1.length; int[] nums1 = new int[n+1]; for (int i = 1; i <= n; i++){ nums1[i] = Integer.parseInt(str1[i-1]); } System.out.println("请输入序列2："); String[] str2 = scanner.nextLine().trim().split(" "); int m = str2.length; int[] nums2 = new int[m+1]; for (int i = 1; i <= m; i++){ nums2[i] = Integer.parseInt(str2[i-1]); } scanner.close(); //dp[i][j]表示两个字符串从头开始，直到第一个串的第i位和第二个串的第j位最多有多少个公共子元素 int[][] dp = new int[n+1][m+1]; for (int i = 1; i <= n; i++){ for (int j = 1; j <= m; j++){ dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); if (nums1[i] == nums2[j]){ dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1] + 1); } } } System.out.println(dp[n][m]); } }

下面在看两道题目进行练习巩固。
一、首先，看一个导弹拦截的问题（http://codevs.cn/problem/1044/）

题目描述 Description

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入描述 Input Description

输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数）

输出描述 Output Description

输出这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

样例输入 Sample Input

389 207 155 300 299 170 158 65

样例输出 Sample Output

6
2

数据范围及提示 Data Size & Hint

导弹的高度<=30000，导弹个数<=20

分析：本题其实就是求解最长降序序列长度（每套系统拦截的导弹数量）和最长升序序列长度（系统数量）

代码如下：

public class Test { public static void main(String[] args) { Scanner scan = new Scanner(System.in); System.out.println("输入导弹依次飞来的高度(中间用空格间隔): "); String[] strs = scan.nextLine().split(" "); int[] high = new int[strs.length]; for (int i = 0; i < strs.length; i++){ high[i] = Integer.parseInt(strs[i]); } scan.close(); //需要的系统数量 int[] d1 = new int[high.length]; //每套系统拦截的导弹数量 int[] d2 = new int[high.length]; int len1 = 1, len2 = 1; d1[0] = 1; d2[0] = 1; for (int i = 0; i < high.length; i++){ d1[i] = 1; d2[i] = 1; for (int j = 0; j < i; j++){ //导弹系统数量——最长升序序列长度 if (high[i] > high[j] && d1[i] < d1[j] + 1){ d1[i] = d1[j] + 1; } if (len1 < d1[i]){ len1 = d1[i]; } //每套系统拦截的导弹数量——最长降序序列长度 if (high[i] <= high[j] && d2[i] < d2[j] + 1){ d2[i] = d2[j] + 1; } if (len2 < d2[i]){ len2 = d2[i]; } } } System.out.println(len2); System.out.println(len1); } }

二、再看一个数字划分问题（http://codevs.cn/problem/1039/）

题目描述 Description

将整数n分成k份，且每份不能为空，任意两种划分方案不能相同(不考虑顺序)。
例如：n=7，k=3，下面三种划分方案被认为是相同的。
1 1 5
1 5 1
5 1 1
问有多少种不同的分法。

输入描述 Input Description

【动态规划算法的理解】输入：n，k (6

输出描述 Output Description

输出：一个整数，即不同的分法。

样例输入 Sample Input

7 3

样例输出 Sample Output

数据范围及提示 Data Size & Hint

{四种分法为：1，1，5; 1，2，4; 1，3，3; 2，2，3; }

分析：
还是使用动态规划算法，将划分后的数字分成包含1和不包含1两种情况。
dp[i][j] = dp[i-1][j-1] + dp[i-j][j]，
即：dp[i][j]表示把数字 i 划分为 j 部分；
dp[i-1][j-1]:划分的j份中至少有一份为1，把这个1拿出来，剩下的相当于把i-1分为j-1份
dp[i-j][j]:划分的j份中没有一份是1，每一份中都拿走1个1，剩下的相当于把i-j分为j份
dp状态一般由前一个状态转移而来的。

代码如下：

public class DivideNum { public static void main(String[] args) { Scanner scan = new Scanner(System.in); System.out.println("请输入数字以及划分数目（中间空格隔开）："); String[] strs = scan.nextLine().split(" "); scan.close(); int n = Integer.parseInt(strs[0]); int k = Integer.parseInt(strs[1]); int[][] dp = new int[n+1][k+1]; //初始化dp，先暂时默认成1部分 for (int i = 0; i < n; i++){ dp[i][1] = 1; } //初始化方案数目为1 int size = 1; for (int i = 1; i <= n; i++){ for (int j = 1; j <=k; j++){ if (i >= j){ dp[i][j] = dp[i-1][j-1] + dp[i-j][j]; } if (size < dp[i][j]){ size = dp[i][j]; } } } System.out.println(size); } }

另外，如果还不太理解的童鞋，可以在在继续看看下面两篇博文：