Fibonacci Number - Leetcode 509 - Dynamic Programming (Python)

Please check my playlists for free DSA problem solutions:

My Favorite Courses:

Data Structures & Algorithms:

Python:

Web Dev / Full Stack:

Cloud Development:

Game Development:

SQL & Data Science:

Machine Learning & AI:

[GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[Rose-gbku]

BEST VIDEO to get started with DP. Thanks a lot <3

[galdali]

Great video! There is another way to solve it by using matrices; take the matrix[[1, 1], [1, 0]] and raise it to the power of n, then multiply it (from the right) by the column vector (1, 0) and take the lower row of this resulting vector. It will be in O(n) run time (to raise the matrix to the nth power (assuming one 2×2 matrix multiplication is in O(1))) and the space complexity is O(1)

[ryuhayabusa]

Very nice explanation, I used a decorator approach to improve performance, but your solutions are amazing

[Pradyumna_P]

I love how he said,
The steps of dynamic programming :
Step 1 - don't use dynamic programming
😂😂

[FrozenKnight]

I kinda did this diffrently, but i guess it amounts to the same thing.

I used an array, with a window, fulled in the first few values, then worked my way backwards.

However, i had to later update it because i didnt realize there are negative fibanati numbers, and computing them is similar but a little trickier. But i did find a good work arround in the end.

[dabisrat]

Great video as always. I was curious why is the golden ratio solution log time? I figured it would be constant time.

[javedmiya]

Can you upload complete one shot python (covering all things required for dsa)