dynamic-programming.md

Dynamic Programming

• Dynamic Programming vs Divide-and-Conquer

  • #Fibonacci, binary search and minimum edit distance [levenshtein-distance]

• Dynamic Programming - Learn to Solve Algorithmic Problems & Coding Challenges YouTube Course - 5 hours

  • #Fibonacci #memoize (see below)
  • Grid memoize (todo)
  • Tabulation (todo)
  • Recipe (todo)

function fib(n) {
    if (n <= 2) {return 1;}
    return fib(n-1) + fib(n-2);
}
//or (my one liner)
//const fib = (n, memo={2:1, 1:1}) => memo[n] || (memo[n] = fib(n-1, memo) + fib(n-2, memo))
const fib = (n, m={2:1, 1:1}) => m[n] || (m[n] = fib(n-1, m) + fib(n-2, m))

// Try time complexity of fib(50)

console.assert(fib(6) == 8)
console.assert(fib(7) == 13)
console.assert(fib(8) == 21)

• Python’s “Disappointing” Superpowers
  • Dynamic programming examples in #python [python]