五⼤常见算法策略之——动态规划策略
（DynamicProgramming）
Dynamic Programming
  Dynamic Programming是五⼤常⽤算法策略之⼀，简称DP，译作中⽂是“动态规划”，可就是这个听起来⾼⼤上的翻译坑苦了⽆数⼈，因为看完这个算法你可能会觉得和动态规划根本没太⼤关系，它对“动态”和“规划”都没有太深的体现。
  举个最简单的例⼦去先浅显的理解它，有个⼤概的雏形，⼀个数组中的最⼤元素，如果只有⼀个元素，那就是它，再往数组⾥⾯加元素，递推关系就是，当你知道当前最⼤的元素，只需要拿当前最⼤元素和新加⼊的进⾏⽐较，较⼤的就是数组中最⼤的，这就是典型的DP策略，将⼩问题的解保存起来，解决⼤问题的时候就可以直接使⽤。
  刚刚说的如果还是感觉有点迷糊，不⽤慌，下⾯⼏个简单的⼩栗⼦让你明⽩这句话的意思。
  第⼀个数是1，第⼆个数也是1，从第三个数开始，后⾯每个数都等于前两个数之和。要求：输⼊⼀个n，输出第n个斐波那契数。
  还是我们上节讨论递归与分治策略时候举的第⼀个例⼦——Fibonacci数列问题，它实在太经典了，所以将其反复拿出来说。
  我们如果深⼊分析⼀下上节说过的递归⽅法解决Fibonacci数列，就会发现出现了很多重复运算，⽐如你在计算f(5)的时候，你要计算f(4)和f(3)，计算f(4)⼜要计算(3)和f(2)，计算f(3)，⼜要计算f(2)和f(1)，看下⾯这个图
对f(3)和f(2)进⾏了重复运算，这还是因为5⽐较⼩，如果要计算f(100)，那你可能要等到天荒地⽼它还没执⾏完（⼿动滑稽），感兴趣的朋友可以试试，反正我已经试过了。
public static int fibonacci(int n){//递归解法
if(n == 1) return 1;
else if(n == 2) return 1;
else return fibonacci(n - 1) + fibonacci(n - 2);
}
上⾯就是递归的解法，代码看着很简单易懂，但是算法复杂度已经达到了O(2^n)，指数级别的复杂度，再加上如果n较⼤会造成更⼤的栈内存开销，所以⾮常低效。
我们再来说说DP策略解决这个问题
我们知道导致这个算法低效的根本原因就是递归栈内存开销⼤，对越⼩的数要重复计算的次数越多，那既然我们已经将较⼩的数，诸如
f(2),f(3)...这些计算过了，为什么还要重复计算呢，这时就⽤到了DP策略，将计算过的f(n)保存起来。我们看看代码：
/**
* 对斐波那契数列求法的优化：如果单纯使⽤递归，那重复计算的次数就太多了，为此，我们对其做⼀些优化
* 假设最多计算到第100个斐波那契数
* ⽤arr这个数组来保存已经计算过的Fibonacci数，以确保不会重复计算某些数
*/
private static int arr[] = new int[100];
public static int Fibonacci(int n){
if(n <= 2){
return 1;
}else{
字符串长度最大是多少if(arr[n] != 0) //判断是否计算过这个f(n)
return arr[n];
else{
arr[n] = Fibonacci(n-1)+Fibonacci(n-2);
return arr[n];
}
}
}
arr数组初始化为0，arr[i]就表⽰f(i)，每次先判断arr[i]是否为0，如果为0则表⽰未计算过，则递归计算，如果不为0，则表⽰已经计算过，那就直接返回。
这样的好处避免了很⼤程度上重复的计算，但是对栈内存的开销虽然有减⼩但还不是很显著，因为只要有递归，栈内存就免不了有较⼤开销。所以针对Fibonacci数列我们还有⼀个递推的⽅式来计算，其实这也符合DP策略的思想，都是将计算过的值保存起来。
//甚⾄可以使⽤递推来求解Fibonacci数列
public static int fibonacci(int n){
if(n <= 2) return 1;
int f1 = 1, f2 = 1, sum = 0;
for(int i = 3; i <= n; i++){
sum = f1+f2;
f1 = f2;
f2 = sum;
}
return sum;
}
⼀个机器⼈每次只能向右或者下⾛⼀步，问它试图到达右下⾓“Finish”，共有多少条不同的路径？(7*3的⽹格)
DP策略类的题最重要是要状态转移⽅程，恰恰也是最难的⼀步。
1、我们通过这个图可以看出其实要到达(i,j)也就两种情况，⼀种是从(i,j-1)向右⾛⼀步到达，另⼀种是从(i-1,j)向下⾛⼀步到达，所以将
这两种情况的路径数相加就是到(i,j)的所有路径数。
由此列出状态转移⽅程：
f(i,j)=f(i-1,j)+f(i,j-1)
2、根据DP的思路，将已经计算过的存储起来并⽤于后⾯复⽤其结果，这⾥我们考虑⽤⼆维数组来存储f(i,j)。
3、问题规模从⼩到⼤计算，⼤规模的问题复⽤⼩规模问题的解进⾏计算。
代码实现
/**
* 此题是求解路径个数，让你从(1,1)⾛到某个特定的位置，求⼀共有多少种⾛法
* @param i
* @param j
* @return
*/
public static int Count_Path(int i, int j){
int result[][] = new int[i][j];
for (int k = 0; k < i; k++) {          //将⼆维数组初始化为1
Arrays.fill(result[k],1);
for (int k = 1; k < i; k++) {
for (int l = 1; l < j; l++){
result[k][l] = result[k-1][l]+result[k][l-1];
}
}
return result[i-1][j-1];
}
  ⼜是那只熟悉的青蛙，和上节递归与分治中相同的例题，⼀只青蛙⼀次可以跳上1级台阶，也可以跳上2级，求该青蛙跳上⼀个n级的台阶共有多少种跳法。详细思路可以看看上⼀篇⽂章——递归与分治策略。
我们下⾯先回顾⼀下上次⽤的递归算法：
public static int Jump_Floor1(int n){
if(n <= 2){
return n;
}else{  //这⾥涉及到两种跳法，1、第⼀次跳1级就还有n-1级要跳，2、第⼀次跳2级就还有n-2级要跳
return Jump_Floor1(n-1)+Jump_Floor1(n-2);
}
}
其实和第⼀个例⼦斐波那契⼀样，之所以把它⼜拉出来讨论，是因为它的递归解法中涉及的重复计算实在太多了，我们需要将已经计算过的数据保存起来，以避免重复计算，提⾼效率。这⾥⼤家可以先⾃⼰试着改⼀下其实和第⼀个例⼦的改进⽅法是⼀样的，⽤⼀个数组来缓存计算过的数据。
/**
* 看完递归的⽅法不要先被它的代码简洁所迷惑，可以分析⼀下复杂度，就会发现有很多重复的计算
* ⽽且看完这个会发现和Fibonacci的递归⽅法有点像
* @⾮递归
*/
private static int result[] = new int[100];
public static int Jump_Floor2(int n){
if(n <= 2){
return n;
}else{
if(result[n] != 0)
return result[n];
else{
result[n] = Jump_Floor2(n-1)+Jump_Floor2(n-2);
return result[n];
}
}
}
下⾯将难度做⼀提升，我们来讨论⼀道DP策略⾥的经典例题——最长公共⼦列问题
给定两个序列，需要求出两个序列最长的公共⼦序列，这⾥的⼦序列不同于字串，字串要求必须是连续的⼀个串，⼦序列并没有这么严格的连续要求，我们举个例⼦：
⽐如A = "LetMeDownSlowly!" B="LetYouDownQuickly!" A和B的最长公共⼦序列就是"LetDownly!"
⽐如字符串1：BDCABA；字符串2：ABCBDAB，则这两个字符串的最长公共⼦序列长度为4，最长公共⼦序列是：BCBA
我们设 X=(x1,x2,.....xn) 和 Y={y1,y2,.....ym} 是两个序列，将 X 和 Y 的最长公共⼦序列记为LCS(X,Y)，
要它们的最长公共⼦序列就是要求最优化问题，有以下⼏种情况：
1、n = 0 || m = 0，不⽤多说最长的也只能是0，LCS(n,m) = 0
2、X(n) = Y(m)，说明当前序列也是相等的，那就给这两个元素匹配之前的最长长度加⼀，即LCS(n,m)=LCS(n-1,m-1)+1
3、X(n) != Y(m)，这时候说明这两个元素并没有匹配上，那所以最长的公共⼦序列长度还是这两个元素匹配之前的最长长度，即
max{LCS(n-1,m)，LCS(n,m-1)}
由此我们可以列出状态转移⽅程：（⽤的别⼈的图）
我们可以考虑⽤⼀个⼆维数组来保存LCS(n,m)的值，n表⽰⾏，m表⽰列，作如下演⽰，⽐如字符串1：ABCBDAB，字符串2：BDCABA；
1、先对其进⾏初始化操作，即将m=0，或者n=0的⾏和列的值全填为0
2、判断发现A != B，则LCS(1,1) = 0，填⼊其中
3、判断B == B，则LCS(1,2) = LCS(0,1)+1=1，填⼊其中

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。