Dynamic Programming Basics

DSA · Dynamic Programming

Theory

Dynamic programming (DP) solves problems that have overlapping sub-problems and optimal substructure by solving each sub-problem once and storing its answer. Top-down DP (memoisation) adds a cache to a recursive solution; bottom-up DP (tabulation) fills a table from the smallest sub-problems upwards. The steps are: define the state, write the recurrence, set base cases, and choose the computation order.

Why we use it

DP turns exponential brute-force solutions into polynomial ones, often O(n) or O(n²).

When to use it

Use DP when a problem asks for a count, minimum, maximum or yes/no answer that can be built from answers to smaller versions, and the same smaller versions repeat.

How it works

  1. Define state dp[i]
  2. Write recurrence from smaller states
  3. Set base cases
  4. Top-down? Yes: Recursion + memo. No: Bottom-up: fill table in order.
  5. Answer = dp[target]

Syntax

Top-down:  memo = {}; def f(n): if n in memo: return memo[n]; ...
Bottom-up: dp = [base]; for i in range(...): dp[i] = recurrence

1. State   2. Recurrence   3. Base cases   4. Order

Example

calls = [0]
def fib_plain(n):
    calls[0] += 1
    return n if n < 2 else fib_plain(n - 1) + fib_plain(n - 2)

memo = {}
def fib_memo(n):
    if n in memo:
        return memo[n]
    memo[n] = n if n < 2 else fib_memo(n - 1) + fib_memo(n - 2)
    return memo[n]

def fib_table(n):
    dp = [0, 1]
    for i in range(2, n + 1):
        dp.append(dp[i - 1] + dp[i - 2])
    return dp[n]

print("Plain fib(20):", fib_plain(20), "with", calls[0], "calls")
print("Memoised fib(80):", fib_memo(80))
print("Tabulated fib(80):", fib_table(80))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic