[用JS來寫演算法和了解資料結構] Day15 動態規劃 Dynamic programming - Closure / Fibonacci numbers

動態規劃 Dynamic programming

• using ‘Cache’ Memoization

動態規劃的基本思想是將「原始問題」分解成多個「子問題」，先求解並「儲存」這些子問題的解到 cache，然後通過這些子問題的解來提供給原問題。這樣做的目的是避免重複計算，從而提高算法的效率。

• Dynamic Programming = Divide-and-Conquer + Memoization (Cache)
  與 分而治之 Divide-and-Conquer 很像，但最大的差別是子問題大多類似，並先儲存子問題的解到 cache，之後需要使用到時就不用重複計算

基本概念

let cache = {}; //cache 儲存先前計算過的結果 下次再使用就從cache取

function memoizeAddTo80(n) {
  if (n in cache) {
    return cache[n];
  } else {
    console.log("first time run");
    const answer = n + 80;
    cache[n] = answer; //儲到cache
    return answer;
  }
}

console.log(memoizeAddTo80(6));
// 'first time run' -> {6: 86} 把這個結果算出並存到
console.log(memoizeAddTo80(6));
// 不用經過'first time run' 就直接取存好的結果

Closure

使用 Closure 讓 cache 可以存於 local scope 中，不外洩。

//cache 儲存先前計算過的結果 下次再使用就從cache取

function memoizeAddTo80() {
  let cache = {};
  return function (n) {
    if (n in cache) {
      return cache[n];
    } else {
      console.log("first time run");
      const answer = n + 80;
      cache[n] = answer; //儲到cache
      return answer;
    }
  };
}

const memoized = memoizeAddTo80();
const memoized2 = memoizeAddTo80(); // 可以創建另一個cache資料庫 而不受影響

console.log(memoized(6));
console.log(memoized(6));

console.log(memoized2(6));
console.log(memoized2(6));

常見運用 Counter

const createCounter = function (n) {
  let count = n;
  return () => count++;
};

const counter = createCounter(10);
counter(); // 10
counter(); // 11
counter(); // 12

const counter2 = createCounter(5);
counter2(); // 5
counter2(); // 6

最經典的例子

費波那契數列 Fibonacci numbers

前面 recursion 有提到的解法 為 O(2^n)
再加上 cache 可讓解法變成 O(n)

// Given a number N return the index value of the Fibonacci sequence,
// where the sequence is:
// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ...
// the pattern of the sequence is that each value is the sum of the 2 previous values, that means that for N=5 → 2+3

// For example:
// input 6
// output 8
// 8 => 5 + 3
//      5 => 3 + 2
//           3 => 2 + 1
//                2 => 1 + 1
//                     1 => 1 + 0

// Recursive 遞迴 O(2^n)
function fibonacciRecursive(n) {
  if (n < 2) {
    return n;
  }
  return fibonacciRecursive(n - 2) + fibonacciRecursive(n - 1);
}
console.log(fibonacciRecursive(6)); //8

// Iterative 迭代 O(n)
function fibonacciIterative(n) {
  let fibonacciArr = [0, 1];
  for (i = 2; i <= n; i++) {
    fibonacciArr[i] = fibonacciArr[i - 1] + fibonacciArr[i - 2];
  }
  return fibonacciArr[n];
}
console.log(fibonacciIterative(6)); //8

Dynamic programming 解法

function fibonacciRecursive() {
  const cache = {};
  return function fib(n) {
    if (n in cache) {
      return cache[n];
    } else {
      if (n < 2) {
        return n;
      } else {
        cache[n] = fib(n - 2) + fib(n - 1);
        return cache[n];
      }
    }
  };
}

const DPfib = fibonacciRecursive();
console.log(DPfib(6)); //8

學習與參考資料

• Master the Coding Interview: Data Structures + Algorithms
• 輕鬆搞懂演算法:動態規劃(Dynamic Programming)
• Data Structures and Algorithms (DSA)