2. FreeCodeCamp - Dynamic Programming - Learn to Solve Algorithmic Problems & Coding Challenges
Dynamic Programming - Parts PART 1 - Memoization P ART 2 - Tabulation Dynamic Programming with Fibonacci Example Recursion: Slow because time complexity is O(2^n) func fibR (x int ) int { if x <= 2 { return 1 } return fibR (x- 1 ) + fibR (x- 2 ) } Dynamic Way Example Recursion with Stored Value: // Fast because it removes duplicate processes by checking map. // Tail recursion-ish // Results are hitchhiking each recursive call func fibR2 (x int , y map [ int ] int ) int { if _ , ok := y[x]; ok { return y[x] } if x <= 2 { return 1 } y[x] = fibR2 (x- 1 , y) + fibR2 (x- 2 , y) return y[x] }
Comments
Post a Comment