美文网首页
动态规划(一)

动态规划(一)

作者: 倚仗听江 | 来源:发表于2020-08-20 09:16 被阅读0次

    动态规划其实和递归或者分治没有根本上的区别(关键是看有无最优子结构)
    共性:找到重复子问题
    差异性:最优子结构、中途可以淘汰次优解

    讲到动态规划,就不得不提到一个经典的问题——斐波那契数列。
    注:有些地方会要求答案取模 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];
        }
    

    这就是动态规划的最简单的应用。

    相关文章

      网友评论

          本文标题:动态规划(一)

          本文链接:https://www.haomeiwen.com/subject/wttdjktx.html