什么是动态规划?

概述


动态规划(Dynamic Programming)是一种分阶段求解决策问题的数学思想,它通过把原问题分解为简单的子问题来解决复杂问题.动态规划在很多领域都有着广泛的应用,例如管理学,经济学,数学,生物学.

动态规划适用于解决带有最优子结构和子问题重叠性质的问题.

  • 最优子结构 : 即是局部最优解能够决定全局最优解(也可以认为是问题可以被分解为子问题来解决),如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质.
  • 子问题重叠 : 即是当使用递归进行自顶向下的求解时,每次产生的子问题不总是新的问题,而是已经被重复计算过的问题.动态规划利用了这种性质,使用一个集合将已经计算过的结果放入其中,当再次遇见重复的问题时,只需要从集合中取出对应的结果.

动态规划与分治算法的区别


相信了解过分治算法的同学会发现,动态规划与分治算法很相似,下面我们例举出一些它们的相同之处与不同之处.

相同点

  • 分治算法与动态规划都是将一个复杂问题分解为简单的子问题.
  • 分治算法与动态规划都只能解决带有最优子结构性质的问题.

不同点

  • 分治算法一般都是使用递归自顶向下实现,动态规划使用迭代自底向上实现或带有记忆功能的递归实现.
  • 动态规划解决带有子问题重叠性质的问题效率更加高效.
  • 分治算法分解的子问题是相对独立的.
  • 动态规划分解的子问题是互相带有关联且有重叠的.

斐波那契数列


斐波那契数列就很适合使用动态规划来求解,它在数学上是使用递归来定义的,公式为F(n) = F(n-1) + F(n-2).

斐波那契数列求解过程

普通递归实现

一个最简单的实现如下.

    public int fibonacci(int n) {
        if (n < 1)
            return 0;
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;

        return fibonacci(n - 1) + fibonacci(n - 2);
    }

但这种算法并不高效,它做了很多重复计算,它的时间复杂度为O(2^n).

动态规划递归实现

使用动态规划来将重复计算的结果具有"记忆性",就可以将时间复杂度降低为O(n).

    public int fibonacci(int n) {
        if (n < 1)
            return 0;
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;

        // 判断当前n的结果是否已经被计算,如果map存在n则代表该结果已经计算过了
        if (map.containsKey(n))
            return map.get(n);

        int value = fibonacci(n - 1) + fibonacci(n - 2);
        map.put(n, value);
        return value;
    }

虽然降低了时间复杂度,但需要维护一个集合用于存放计算结果,导致空间复杂度提升了.

动态规划迭代实现

通过观察斐波那契数列的规律,发现n只依赖于前2种状态,所以我们可以自底向上地迭代实现.

    public int fibonacci(int n) {
        if (n < 1)
            return 0;
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;

        // 使用变量a,b来保存上次迭代和上上次迭代的结果
        int a = 1;
        int b = 2;
        int temp = 0;

        for (int i = 3; i <= n; i++) {
            temp = a + b;
            a = b;
            b = temp;
        }

        return temp;
    }

这样不仅时间复杂度得到了优化,也不需要额外的空间复杂度.

参考资料


本文作者为SylvanasSun(sylvanassun_xtz@163.com),转载请务必指明原文链接.

最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 《算法导论》这门课的老师是黄刘生和张曙,两位都是老人家了,代课很慢很没有激情,不过这一章非常有意思。更多见:iii...
    mmmwhy阅读 5,517评论 5赞 31
  • 下面是王晴儿为大家简单分享的一份医院/医疗医药网站建设制作开发建站解决方案! 一、概述 医院网站的作用更类似于医院...
    设计师王晴儿阅读 1,281评论 0赞 50
  • 今天是你的生日,我的花花姐姐。在这个静静地,多情写意的秋里你迎来了61岁生日。 你7岁那年,我们在长航那简陋...
    秋荷浴雨阅读 337评论 0赞 1
  • 国庆第四天,现在坐在古城的江边,看到的是美景,心情却是复杂的,经过昨天的谈心,我才认识到每个人都是独立的,,而且一...
    清风腾逸阅读 719评论 0赞 51
  • 土地翻了翻身种子开始按耐不住内心的喜悦 贫穷在田头凝望着远方的城市 田间拿着锄头的老汉擦拭着额头的汗水 土地是幸福...
    心花园子阅读 274评论 0赞 4

友情链接更多精彩内容