Python-Learning-Grounds/DynamicPrograms.py at main · DanteVela/Python-Learning-Grounds · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
# This script demonstrates how to solve Dynamic Programming Problems.
# -------------------------------------------------------------------------------------------------------------------------------
# 1) Recursive Backtracking
def f(n):
    if n == 0: return 0
    if n == 1: return 1

    return f(n-1) + f(n-2)

# Time: O(2^n)
# -------------------------------------------------------------------------------------------------------------------------------
# 2) Top-Down DP (Memoization)
def fib(n):
    memo = {0:0, 1:1}

    def f(n):
        if n in memo:
            return memo[n]

        memo[n] = f(n-1) + f(n-2)
        return memo[n]

    return f(n)

# Time: O(n)
# -------------------------------------------------------------------------------------------------------------------------------
# 3) Bottom-Up DP (Tabulation)
def fib(n):
    dp = [0, 1]

    for i in range(2, n+1):
        new = dp[i-2] + dp[i-1]
        dp.append(new)

    return dp[n]

# Time: O(n)
# -------------------------------------------------------------------------------------------------------------------------------
# 4) Bottom-Up, No Memory DP
def fib(n):
    if n < 2: return n

    prev, cur = 0, 1
    for i in range(2, n+1):
        prev, cur = cur, cur + prev

    return cur

# Time: O(n)
# -------------------------------------------------------------------------------------------------------------------------------