动态规划其实和递归或者分治没有根本上的区别(关键是看有无最优子结构)
共性:找到重复子问题
差异性:最优子结构、中途可以淘汰次优解
讲到动态规划,就不得不提到一个经典的问题——斐波那契数列。
注:有些地方会要求答案取模 1e9+7(1000000007),这里就不考虑这个问题啦。
如果不使用动态规划,直接递归的话,代码可以是这样的
public static int fib(int n) {
return n <= 1 ? n : fib(n - 1) + fib(n - 2);
}
这样的情况下,算法的时间复杂度达到了指数级,效率很低,因为它进行了很多重复性的计算。所以我们就自然而然的想到了,那能否不做这些重复性的计算呢?答案是可以的。我们可以使用一个数组,来存储我们计算出来的数据。当需要再次计算这个值的时候,直接从数组中拿就好了,算是一种空间换时间的记忆化搜索吧。
public static int fib(int n,int[] memo) {
if (n<=1) return n;
if (memo[n] == 0) {
memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
}
return memo[n];
}
这样算法的时间复杂度就变成了O(n),从指数级转变成了线性的,算法的效率大大提高了!
那能否继续优化这个算法呢?答案依然是可以的,其实人脑对于这种问题很多时候会采用自顶向下的递推,什么意思呢?比如说:你要计算fib(6)的值,那你可能会想,要计算fib(6)就要先算fib(5)和fib(4),要算fib(5)和fib(4)又要先算fib(3)和fib(2)......这就是自顶向下的递推,那我们可以换一种思路,自底向上进行递推,从fib(0)和fib(1)递推到fib(n),也就解决了问题,代码是这样的:
public static int fib(int n,int[] dp) {
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
这就是动态规划的最简单的应用。
网友评论