Leetcode-Dynamic Programming

Dynamic Programming is an algorithm combines [1]

  1. correctness of complete search
  2. efficiency of greedy algorithm

There’ re two use cases for DP problem:

  1. Finding an optimal solution: We want to find a solution that is as large as possible or as small as possible.
  2. Counting the number of solutions: We want to calculate the total number of optimal solutions.

What’s the main difference between greedy algorithm and dynamic programming is

DP could be applied, only if the main problem can be divided into overlapping subproblems that can be solved independently.

That’s the core idea of dynamic programming, which is essentially different from greedy’s core idea. [2]

Why we introduce a memorization table in DP algorithm?

Because overlapping subproblem properties, with memorization table, so that we calculate those answers to subproblems only once.

When implementing,

  1. we will formulate core idea of DP into recursive formulation mathematically. (Key part to solve DP problem)
  2. We usually use array as a memorization table to store solution to subproblem to avoid recomputing(thus providing efficiency).

For using dynamic programming to solve problem, there are 3 steps to think about:

Step0 . To recognize it might be a DP problem and describe brute force solution verbally during the interview.

Step1. Think about what’s base case.

Step2. Think about how do we formulate core idea into recursive formulation mathematically usually by observing relationship between current subproblem and previous subproblem.

Step3. Think about how to return our target from our memorization table usually by taking the last cell in memorization table as our target.

Notes:

  1. For optimization problems, it’s crystal clear signal to show it’s able to use DP or Greedy algorithm to solve it. And, in practice, Greedy might be more efficient than DP from time complexity perspective, to reduce it from O(n²) to O(nlogn). Please refer to leetcode 300 and 673.
  2. However, Greedy algorithms that make the locally optimal solution at each step are typically efficient but usually do not guarantee global optimality because it might require the proof that always return the best possible solution. [3] Please refer to leetcode 322. That’s why it works only in DP.
  3. For bottom-up DP approach, must make sure that you solved each previous subproblems already.
  4. For classical Fibonacci DP problem, please refer to LC 70 and LC 509.
  5. When we must need 2-D Dp instead of 1-D Dp?
  6. Summarise all possible transition function in DP problem.

The below are some DP problems in Leetcode:

Reference:

[1]. Chapter 7, Competitive programmer handbook https://github.com/abhishekgahlot/competitive-programmer-handbook-python

[2]. https://medium.com/@ray811030/leetcode-greedy-algor-1c9fc0097689

[3]. Chapter 8, The algorithm design manual, 2nd edition

https://github.com/aforarup/interview/blob/master/Data%20Structures%20and%20Algorithm/Algorithm%20Books/The%20Algorithm%20Design%20Manual%20by%20Steven%20S.%20Skiena.pdf

I’m Taiwanese expat. I’v worked in Singapore as data scientist after graduation from Taiwan and currently I work in Amsterdam as machine learning engineer.