当遇到复杂问题时我们经常会通过递归的方式将大事化小，小事化了。但是有时候将复杂问题简单地分解成几个子问题，问题求解耗时会按问题规模呈幂级数增加。这时候为了节约重复求相同子问题的时间，引入一个数组(或临时变量)，不管它们是否对最终解有用，把所有子问题的解存于该数组(或临时变量)中，这就是动态规划的基本思想。
1.Fibonacci数列
该数列的递归形式如下，即从每二项开始每一项等于前两项之和：
根据定义可以用递归方式写出如下代码：
public int fib(int n) { // 计算Fibonacci数列的第n项（二分递归版）：O(2^n)
return (2 > n) ? n // 若到达递归基，直接取值
: fib(n - 1) + fib(n - 2); // 否则，递归计算前两项，其和即为正解
}
递规版本的时间复杂度将呈指数级别，明显不能很好的解决问题，现通过牺牲空间复杂度，利用动态规划的思想将时间复杂度控制降低到O(n).
public static int fib1(int n) { // 计算Fibonacci数列的第n项（动态规划版）：O(n)
if(n < 2) return n;
int a = 0;//第一个值
int b = 1;//第二个值
int tmp = 0;//辅助变量
for(int i = 2;i <= n;i++){
tmp = a + b;
a = b;
b = tmp;
}
return tmp;
}
2.爬楼梯
问题描述：有一座高度为n级的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶，求出一共有多少种走法。
分析：因为每1步只能走1级或者2级，所以走到第n级的前一步有且只有两种情况，第一种情况是从第n - 1级走1级，第二种情况是从第n - 2级走2级。由此我们就可以得到此问题的递归公式：
F(1) = 1;
F(2) = 2;
F(n) = F(n - 1) + F(n - 2);
看到这里，相信聪明的你很快就反映过来了这不就是上面的Fibonacci数列问题嘛(注意：起始值不同)，下面直接给出动态规划思想的代码实现:
public static int getNum(int n) {
if(n <= 2) return n;
int a = 1;//只有1级台阶的情况
int b = 2;//有2级台阶的情况
int tmp = 0;//辅助变量
for(int i = 3;i <= n;i++){
tmp = a + b;
a = b;
b = tmp;
}
return tmp;
}
3.最长公共子序列
有了上面两个动态规划实现的热身，下面看一个复杂点的问题，首先看一下两个定义：
子序列(Sequence)：由序列中若干字符，按原相对次序构成。
最长公共子序列(Longest Common Subsequence）:两个序列公共子序列中的最长者，下面简称LCS,可能出现下面两种比较复杂的情况：
1).可能有多个
2).可能有歧义
现用递归的思想分析如下：
对于序列A[0,n]和B[0,m]，LCS(A,B)无非三种情况：
- 若n = - 1或 m = - 1，则取作空序列("")
- 若A[n] = ‘X' = B[m],则取作LCS(A[0,n), B[0,m)) + 'X',示意图如下：
-
若A[n] != B[m],则在LCS(A[0,n], B[0,m))与LCS(A[0,n), B[0,m])中取更长者
示意图如下：
如下图所示，展示了“EDUCATIONAL”和“ADVANTAGE”通过递归思想求最长公共子序列的过程。
代码实现如下：
/**
* 递归方式实现求两个字符串最长公共字序列的长度
* @param str1 第一个字符串
* @param m 第一个字符串需要比较的长度
* @param str2 第二个字符串
* @param n 第一个字符串需要比较的长度
* @return
*/
public static int lcs(String str1,int m,String str2,int n){
if(m == 0 || n == 0) return 0;//如果其中有一个元素为空则返回0
if(str1.charAt(m - 1) == str2.charAt(n - 1))
return lcs(str1,m - 1,str2,n - 1) + 1;//如果需要比较的两个字符串最后一个字符相同则将问题缩小
//剩下的情况则两个字符串的最后一个字符不相等，取两种情况中的最大值
return getMax(lcs(str1,m - 1,str2,n),lcs(str1,m,str2,n - 1));
}
可以看出如果最后一个字符不相等，反而会将问题的规模扩大，当m与n大小接近时，时间复杂度也呈指数级别。下面将考虑通过动态规划的思想来实现：
构造一个二维辅助数组，从上往下依次计算，如下图所示：
代码实现如下：
/**
* 非递归方式实现求两个字符串最长公共字序列的长度
* @param str1 第一个字符串
* @param m 第一个字符串需要比较的长度
* @param str2 第二个字符串
* @param n 第一个字符串需要比较的长度
* @return
*/
public static int lcs1(String str1,int m,String str2,int n){
if(m == 0 || n == 0) return 0;
//构建一个m + 1行 n + 1列的辅助二维数组,里面的元素初始值都为0
int[][] arr = new int[m + 1][n + 1];
//依次求二维数组中的值
for(int i = 1;i <= m;i ++){
for(int j = 1;j <= n; j ++){
//当最后一个字符相等时等于左上角的元素加1
if(str1.charAt(i - 1) == str2.charAt(j - 1)) arr[i][j] = arr[i - 1][j - 1] + 1;
//不相等时取紧邻左边元素和上边元素者的大者
else arr[i][j] = getMax(arr[i - 1][j],arr[i][j - 1]);
}
}
return arr[m][n];//二维数组右下角的元素即我们需要的值
}
总结：动态规划的思想通过牺牲空间复杂度的方式来大大减小时间复杂度，将自顶而下的计算方式改为自底而上，把已计算过的实例结果制表备查，从而取得非常显著的效果。
网友评论