Day25:Dynamic Programming(DP) - 动态规划(上)

https://ithelp.ithome.com.tw/upload/images/20210925/20128604fWcounn5sT.jpg
在认识动态规划之前先来理解Divide and Conquer(分治法)吧!Divide and Conquer是一种演算法,执行的步骤如下

  1. Divide:先将大问题不断切割成小问题
  2. Conquer:用递回的方式处理所有的子问题
  3. Combine:将所有的结果合并起来就是最终解答

动态规划的概念与Divide and Conquer的概念相似,会将大问题切割成多个小问题,再将小问题的解答组合起来,不过有些小问题其实是重复的,所以会发生重复计算的问题,这时候动态规划就会把已经计算过的答案存起来,用空间换取时间,加速执行时间,这就是动态规划的核心精神所在。

斐波那契数列

斐波那契数列由0和1开始,之後的斐波那契数列就是由前两位数字相加而得出 ,也就是第n项为第n-1和第n-2项的总和 - 引用自wikipedia

https://ithelp.ithome.com.tw/upload/images/20210925/20128604Zaxv65OFOB.png
图片来源:https://www.mathsisfun.com/numbers/fibonacci-sequence.html
ex. 89 = 55+34 (n11 = n10 + n9)

下图是斐波那契数列递回执行的流程图,每个方格都是一个函式,观察下图就会发现有不少重复计算的现象,因此时间复杂度为O(2ⁿ)。

https://ithelp.ithome.com.tw/upload/images/20210925/201286044aTEujsAkl.png
图片来源:https://tarjotin.cs.aalto.fi/CS-A1140/2020/notes/dynprog-dp.html

用js实作如下

const fibonacci = (i) => {
    if (i === 0 || i === 1) return i;
    return fibonacci(i - 1) + fibonacci(i - 2);
};

fibonacci(5);

而下图是Dynamic Programming执行的流程,因为蓝色区块已经计算过,并将计算结果暂存起来,所以黄色的区块不需要重复计算,时间复杂度为O(n)。

https://ithelp.ithome.com.tw/upload/images/20210925/20128604fVNmt40frX.png
图片来源:https://tarjotin.cs.aalto.fi/CS-A1140/2020/notes/dynprog-dp.html

为甚麽称为动态规划?

因为宣告存放计算结果的阵列长度是随着输入的长度变化,存放的方式又分为两种 Bottom UpTop Down

  • Bottom Up : 使用回圈,执行顺序是由下至上,又称为Tabulation,可以想成是从小的问题开始计算,逐步计算到最终要求的值,缺点是可能会计算到没有用到的子问题。

  • Top Down : 使用递回,执行顺序是由上至下,计算过的结果会存起来不会重复计算,这个方法也被称作memoization,由於递回的执行效率相较於回圈会来的差,因此这种方法会比Bottom Up还要慢,可能会有递回过深的问题。

用js实作Bottom Up

const fibonacci = (n) => {
    let temp = new Array(n);
    temp[0] = 0;
    temp[1] = 1;
    for (let i = 2; i < n; i++) {
      temp[i] = temp[i-1] + temp[i-2];
    }
    return temp[n-1] + temp[n-2]
  }

  fibonacci(6);//输出8

用js实作Top Down

const fibonacci = (n) => {
    return helper(n, new Array(n));
};
const helper = (i, temp) => {
    if (i === 0 || i === 1) {
        return i;
    }
    if (!temp[i]) {
        temp[i] = helper(i - 1, temp) + helper(i - 2, temp);
    }
    return temp[i];
};

fibonacci(6); //输出8

两者的差异比较如下
https://ithelp.ithome.com.tw/upload/images/20210925/20128604erLIaWe3tb.png
图片来源:https://www.geeksforgeeks.org/tabulation-vs-memoization/

动态规划适用的情境

  1. 最佳子结构 (Optimal Substructure):问题的最佳解可以从子问题的最佳解推算出来。
  2. 重叠子问题 (Overlapping Sub-problems):如斐波那契数列出现重复子问题的情形,动态规划的优势是可以储存过计算过的结果,再次遇到相同子问题的时候直接取出储存的结果,无需重复计算。
  3. 无後效性(no aftereffect):即子问题的解一旦确定,就不再改变,不受在这之後、包含它的更大的问题的求解决策影响。

参考资料:dynamic-programming-laughlin-lunch-and-learn
tabulation-vs-memoization
Overlapping Subproblems Property in Dynamic Programming
动态规划


<<:  透过 Kolla-Ansible 跟 Container 部署 OpenStack

>>:  Day 10 - 密码破解 101

【图解演算法教学】Bubble Sort 的大队接力赛

Youtube连结:https://bit.ly/38xDPdR 这次首次尝试以「动画」形式,来演...

Day 29|Divi 功能练习 21 Fullwidth Menu Module 全宽选单设定

嗨呦大家好我是 Jasmine~脑袋总是胡思乱想停不下来的设计师一枚\(✪ω✪)/ 昏昏沈沈的礼拜一...

Day 04 : 操作基础篇 1 — 认识 Obsidian 预设介面与基础功能

前言 从这篇文章开始,我们要进入到 Obsidian 的操作了。在正式开始教学之前,我先快速简介 O...

Navicat Premium 15 永久激活

Navicat premium是一款数据库管理工具,是一个可多重连线资料库的管理工具,它可以让你以单...

通过 ESG 保证增加价值的 3 种方法

环境、社会和治理 (ESG) 保证正日益成为全球组织关注的焦点——稽核团队需要做好应对的准备。 投资...