Skip to content
Home Tutorials Roadmaps Courses Classroom Training Blog
Log in Join free
Computer Science Beginner Free

Dynamic Programming Introduction

Lesson 14 of 17 · Dynamic Programming 82%
1. Introduction to CS
What is Computer Science?
6. Operating Systems
OS Fundamentals
7. Cybersecurity Basics
Security Fundamentals
8. Software Engineering
Software Development Life Cycle
9. Cloud Computing
Cloud Computing Basics
10. Dynamic Programming
Dynamic Programming Introduction
11. AI & Machine Learning
Introduction to AI & ML
12. Internet of Things
IoT Fundamentals
13. Blockchain Basics
How Blockchain Works

Dynamic Programming solves complex problems by breaking them into overlapping subproblems and storing results.

Two Approaches

  • Top-Down — Memoization (recursive + cache)
  • Bottom-Up — Tabulation (iterative + table)

Syntax

COMPUTER-SCIENCE
# Fibonacci — Naive O(2^n)
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)

# Fibonacci — DP O(n)
def fib_dp(n):
    dp = [0] * (n+1)
    dp[1] = 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]
Fibonacci with Memoization
PYTHON
# Naive recursion O(2^n)
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n-1) + fib_naive(n-2)

# With memoization O(n)
def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

print(f"fib(10) = {fib_memo(10)}")
print(f"fib(30) = {fib_memo(30)}")

Practice

1
Exercise

When should you use dynamic programming?

Answer
When the problem has overlapping subproblems and optimal substructure.

Quick Quiz

1

What is memoization?

Memoization stores results of expensive function calls to avoid recomputation.

Choose an answer to continue.

Interview Questions

Memoization is top-down (recursive + cache). Tabulation is bottom-up (iterative + table). Tabulation is often more space-efficient.

Up next

Introduction to AI & ML

Lesson 15 of 17 · AI & Machine Learning