Sign in
Skip to solution
hardDSA

What is dynamic programming?

1.2k views
01

Understand the problem

Explain DP, memoization, and tabulation.

dynamic-programming
02

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

Dynamic programming solves problems with overlapping subproblems and optimal substructure by storing subproblem results. Memoization is top-down recursion with a cache; tabulation is bottom-up filling a table. Classic examples: Fibonacci, knapsack, longest common subsequence, edit distance.

Solution ready — 2 min read

Classified // press E to declassify

04

Read the code

Fibonacci — naive vs memo vs tabulation
Run Playground
# O(2^n) - recomputes overlapping subproblems
def fib_naive(n):
    return n if n < 2 else fib_naive(n - 1) + fib_naive(n - 2)

# O(n) top-down memoization
def fib_memo(n, cache={}):
    if n < 2: return n
    if n not in cache:
        cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]

# O(n) time, O(1) space bottom-up
def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a


# --- demo ---
print(fib_naive(10), fib_memo(10), fib(10))   # 55 55 55
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

No responses yet. Be the first to share what you think.

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 101 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track