[MasterThe Coding Interview]Algorithms:DynamicProgramming

發表於 分類於 閱讀次數：

本篇為MasterThe Coding Interview教學影片筆記文

假設今天有一個function可以幫我們把數字加10，當我們輸入5的時候，他會輸出15，輸入3會輸出13等，儘管帶入的數字一樣，每執行一次函式，就會重新計算一次結果。如果今天這個function的計算需要花很長一段時間，透過原本的方法就會多了很多不必要的等待，這時候就可以用Dynamic programming的技巧，簡單來說就是把已經計算過的輸出記錄起來，避免掉二次、三次的重工。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
let cache = {}
function memoizedAddTo10(n){
	if(!(n in cache)) 
		cache[n] = n + 10;
		return cache[n]	
}
memopizedAddTo10(5);
memopizedAddTo10(5);

//上面的方法雖然可以解決問題，但我們需要一個cache的全域變數
//下面示範透過closure來避免掉全域變數

function memoizedAddTo10(){
	let cache = {}
	return function(n){
		if(!(n in cache)) 
			cache[n] = n + 10;
		return cache[n]	
	}
}
const memoized = memoizedAddTo10();
memoized(5);
memoized(5);

只要問題符合以下五個條件，就可以嘗試用Dynamic programming解決：

  1. Can be divided into subproblem
  2. Recursive Solition
  3. Are there repetitive subproblem
  4. Memoize subproblem
  5. Demand a raise from your boss

Exercise： Fibonacci

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function fibonacciMaster(){ //O(n)
	let cache = {}
	return function fib(n){
		if(n in cache) 
			return cache[n]
		if(n < 2) 
			return n
		else{
			cache[n] = fib(n - 1) + fib(n - 2);
			return cache[n];
		}
	}
}
const fibonacci = fibonacciMaster();
fibonacci(10)