A Shopee Code League Experience
Yes, that is what we placed on the leaderboard, based on the 2/5 questions we solved.
- Have 0 expectations — only wanted free merch
- It is always more fun with friends, donuts and crossaints
- Order by level_of_difficulty ASC;
python code noobs (like us) learn > recursion > dynamic programming
What we know: lists and tuple lookups are sequential (i.e. if the stars did not align and what I wanted to find was at the last index, it would take a long time); dictionaries use keys and looking this up does not take into account how much data i have.
What is recursion? It’s a function that calls itself.
How is this different from dynamic programming?
DP may or may not use recursion. If it uses recursion, it will also use memoization (not the same as memorisation!!). Essentially it caches/stores whatever you’ve calculated before. We can see how this is faster if it keeps calling itself, as we don’t have to recalculate the steps again.
DP breaks the solution down into sub problems to find the optimal solution.
In terms of time complexity, DP follows linear time and recursion follows exponential time.
DP is definitely faster, but the time taken for me to write a DP code vs a normal one, would also follow exponential time.