# Leetcode-Dynamic Programming

Dynamic Programming is an algorithm combines [1]

- correctness of complete search
- efficiency of greedy algorithm

There’ re two use cases for **DP problem**:

**Finding an optimal solution**: We want to find a solution that is as large as possible or as small as possible.**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 problemcan be divided into overlappingsubproblemsthat 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,

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

For using

dynamic programmingto solve problem, there are 3 steps to think about:Step0 . To recognize it might be a DP problem and describe

brute forcesolutionverballyduring the interview.Step1. Think about what’s base case.

Step2. Think about how do we formulate

core ideaintorecursive formulation mathematicallyusually by observingrelationship between current subproblem and previous subproblem.Step3. Think about how to return our

targetfrom ourmemorization tableusually by taking the last cell in memorization table as our target.

Notes:

- 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. - 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. - For bottom-up DP approach, must make sure that you solved each previous subproblems already.
- For classical Fibonacci DP problem, please refer to LC 70 and LC 509.
- When we must need 2-D Dp instead of 1-D Dp?
- 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