LeetCode - 10 Essential DP Patterns

These days, I’m working hard to solve algorithm problems with Python. There are lots of platforms we can choose, such as Baekjoon or Programmers. These two websites are popular online algorithm websites in korea. Well there are many alternatives other than these two, such as Topcoder, Codeforces and Atcoder. These are very competitive algorithm contest websites. However if you want to improve your algorithm programming skills, LeetCode would be a great choice.

About LeetCode

LeetCode provides variety of problems and each of them is classified as Easy/Medium/Hard diffifulty. I recommend to solve the problems listed in Study Plan because they categorize problems into algorithm types very well. In my case, I started with Dynamic Programming study plan, and kept solving problems.

10 Essential DP Patterns

The first chapter of ‘10 Essential DP Patterns’ is Fibonacci style. Fibonacci is a sequence which current element is sum of (current-1) and (current-2) elements. The math expression is the following. $ a_{n} = a_{n-1} + a_{n-2} (for n >= 2, a_{0}=1, a_{1}=1 )$

Fibonacci Problems Approaches

There are many approaches to solve fibonacci problems, which are recursion memoization tabulation and space optimization. Recursion is not recommended because of TLE. It has exponential time complexity $ O(2^n) $ . In my case, I prefer to solve problems with tabulation approach, but sometimes I like to solve with space optimization method.

Tabulation Approach

def tabulation(self, n: int) -> int:
    dp = [1,1] + [0]*n # first and second element are 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

Space Optimization

def space_optimization(self, n: int) -> int:
    prev,curr = 1,1 # first and second element are 1
    for _ in range(2, n+1): # _ because we don't need index number
        prev,curr=curr,prev+curr
    return curr

Conclusion

Well, the above approaches are all you need to solve fibonacci problems. If you have understanding of problem, any problems are solved by simple algorithms. So, whenever you are trying to solve difficult problems seperate them into small pieces.