Skip to content

NOTE.md

Latest commit

 

History

History
145 lines (124 loc) · 5.29 KB

NOTE.md

File metadata and controls

145 lines (124 loc) · 5.29 KB

06

Dynamic Programming

  • Optimal Substructure: the solution to a given optimization problem can be obtained by the combination of optimal solutions to its sub-problems. Such optimal substructures are usually described by means of "recursion".

  • Overlapping Subproblems: the space of sub-problems must be small, that is, any recursive algorithm solving the problem should solve the same sub-problems over and over, rather than generating new sub-problems. If a problem can be solved by combining optimal solutions to non-overlapping sub-problems, the strategy is called "divide and conquer" instead.

This can be achieved in either of two ways:

  1. Top-down: Recursion + Memo
  2. Bottom-up: Iteration + DP Table (states)

Fibonacci sequence

Top-down

                            _________________f(5)________________
                           /                                     \
                  _______f(4)______                       _______f(3)_
                 /                 \                     /            \
        _______f(3)_             __f(2)_             __f(2)_          f(1)
       /            \           /       \           /       \
   __f(2)_          f(1)      f(1)      f(1)      f(1)      f(1)
  /       \
f(1)      f(1)

Recursion

def fib(N):
    if N < 2: return N
    return fib(N-1) + fib(N-2)

Space Optimization (Memo)

memo = {}
def fib(N):
    if N < 2: return N
    if N not in memo:
        memo[N] = fib(N-1) + fib(N-2)
    return memo[N]

Bottom-up

f(0) f(1) f(2) f(3) f(4) f(5)
  1    2    3    5    8   13
--------------------------->

Dynamic Programming

def fib(N):
    """
    dp(N) = {
        N, N < 2
        dp(N-1) + dp(N-2), N >= 2
    }
    """
    if N < 2: return N
    dp = [0] * (N+1)
    dp[0] = 0
    dp[1] = 1
    for i in range(2, N+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[-1]

Space Optimization (Reduce States)

def fib(self):
    if N < 2: return N
    f, f1, f2 = 0, 0, 1
    for i in range(N):
        f = f1 + f2
        f2 = f1
        f1 = f
    return f

DP Framework

# initialize base case
dp[0][0][...] = base

# status transfer
for status_1 in all_values_in_status_1：
    for status_2 in all_values_in_status_2:
        for ...
            dp[status_1][status_2][...] = choose(choice_1，choice_2...)

Leetcode Problems

Basics

House Robber

Unique Paths

Sub Array / Sub Subsequence

Buy and Sell Stocks

Greedy Algorithm

A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage.

Leetcode Problems