五⼤常见算法策略之五⼤常见算法策略之——动态规划策略动态规划策略
((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,则表⽰已经计算过,那就直
接返回。