What is dynamic programming in simple words?
Imagine that you are calculating the factorial of the number 5.
To do this, you need: 5 × 4 × 3 × 2 × 1. And now you are asked to calculate the factorial of 6. It's silly to recalculate everything, isn't it? You already know that 5! = 120, just multiply by 6.
Dynamic Programming (DP) — this is exactly the same approach: we solve a complex problem by breaking it down into subtasks, and we remember the results, so as not to count the same thing twice.
The main signs of tasks on the DP:
🎯 Optimal substructure
The solution of a big problem consists of solutions of small subproblems
🔄 Overlapping subtasks
The same subtasks occur many times
⚡ We need to find the optimum
Maximum, minimum or number of methods
Two approaches to DP: memoization and tabulation
1. Memorization (top to bottom)
This is recursion + caching of results. We start with a big task and go down to the basic cases.
def fibonacci_memo(n, memo={}):
# Basic cases
if n <= 1:
return n
# Checking cache
if n in memo:
return memo[n]
# Calculate and save
memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
return memo[n]
print(fibonacci_memo(50)) # Instantly!When to use: when the logic of the task is intuitively understood through recursion.
2. Tabulation (bottom to top)
We build a table of solutions from basic cases to the final answer. No recursion!
def fibonacci_table(n):
if n <= 1:
return n
# Creating a table
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1
# Fill in from bottom to top
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
print(fibonacci_table(50))When to use: when you need maximum performance and memory control.
Classic DP problems you need to know in 2026
Task 1: Fibonacci Numbers
Complexity without DP: O(2ⁿ) — exponential!
Difficulty with DP: O(n) is linear!
We have already seen the solution above. This is the perfect task to start with.
Problem 2: Knapsack Problem
You are a robber with a backpack capacity of W. There are items with weight and value. How do you take the maximum value?
def knapsack(weights, values, capacity):
n = len(weights)
# dp[i][w] = maximum value for i items and w capacity
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(1, capacity + 1):
# We do not take the item
dp[i][w] = dp[i-1][w]
# We take the item if it fits
if weights[i-1] <= w:
dp[i][w] = max(
dp[i][w],
dp[i-1][w - weights[i-1]] + values[i-1]
)
return dp[n][capacity]
weights = [1, 2, 3, 5]
values = [10, 5, 15, 7]
capacity = 7
print(knapsack(weights, values, capacity)) # 32Application in reality: resource allocation, budget planning, server load optimization.
Problem 3: Longest Common Subsequence (LCS)
Find the longest common subsequence of two strings. The basis for git diff!
def lcs(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
print(lcs("ABCDGH", "AEDFHR")) # 3 (ADH)Application: version control systems, plagiarism check, bioinformatics (DNA comparison).
Task 4: Coin Change
There are coins of different denominations. How many ways can you collect the amount?
def coin_change(coins, amount):
# dp[i] = minimum number of coins for the sum i
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # For the amount of 0, you need 0 coins
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
coins = [1, 2, 5]
amount = 11print(coin_change(coins, amount)) # 3 (5+5+1)Application: fintech applications, cash systems, transaction optimization.
Problem 5: Edit Distance (Levenshtein Distance)
The minimum number of operations to convert one string into another.
def edit_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Initialization
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
# Filling in the table
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(
dp[i-1][j], # removal
dp[i][j-1], # insert
dp[i-1][j-1] # replacement
)
return dp[m][n]
print(edit_distance("kitten", "sitting")) # 3Application: correction of typos, search engines, autocomplete.
Step-by-step methodology for solving problems on DP
Step 1: Find a recursive solution
First, just solve the problem with recursion without thinking about optimization.
# Non-optimized versiondef fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)Step 2: Add memoization
Add a dictionary to store results.
def fib_memo(n, memo={}):
if n <= 1:
return n
if n not in memo:
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]Step 3: Convert to tab (optional)
Translate to an iterative approach with an array.
def fib_table(n):
if n <= 1:
return 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]Step 4: Optimize memory
O(1) memory can often be used instead of O(n).
def fib_optimized(n):
if n <= 1:
return n
prev2, prev1 = 0, 1
for _ in range(2, n + 1):
current = prev1 + prev2
prev2, prev1 = prev1, current
return prev1Key DP patterns in 2026
1D DP
One-dimensional array
Fibonacci numbers
Climbing Stairs
House Robber
2D DP
Two-dimensional array
Longest Common Subsequence
Edit Distance
Knapsack Problem
DP on lines
Text processing
Palindrome Subsequences
String Matching
Wildcard Matching
DP on trees
Tree structures
Binary Tree Maximum Path Sum
Diameter of Binary Tree
DP on graphs
Graph algorithms
Shortest Path (Bellman-Ford)
Traveling Salesman Problem
Typical mistakes of beginners
Mistake 1: Forgetting basic cases
def fib(n):
return fib(n-1) + fib(n-2)
# Endless recursion!Correct
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)Error 2: Incorrect table size
dp = [0] * n
# If you need indexes 0..n,
# size n+1 is required!Correct
dp = [0] * (n + 1)Mistake 3: Not checking the boundaries
if dp[i-1]:
# What if i = 0?Correct
if i > 0 and dp[i-1]:Practical tips for interviews.
Draw a table on paper — visualization helps to find dependencies
Start with small examples — fib(0), fib(1), fib(2)...
Look for the recurrence formula — how does dp[i] depend on the previous values?
Say the logic out loud - this shows the course of your thoughts
Don't be afraid to write a suboptimal solution first - then it can be improved
JavaScript version for web developers.
Many beginners work with JavaScript, so here is an example in JS:
// Memorizationfunction fibMemo(n, memo = {}) {
if (n <= 1) return n;
if (memo[n]) return memo[n];
memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
return memo[n];
}
// Tabulationfunction fibTable(n) {
if (n <= 1) return n;
const dp = new Array(n + 1).fill(0);
dp[1] = 1;
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
// Optimized version (O(1) memory)function fibOptimized(n) {
if (n <= 1) return n;
let prev2 = 0, prev1 = 1;
for (let i = 2; i <= n; i++) {
const current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
console.log(fibOptimized(50)); // 12586269025Conclusion.
Dynamic programming is not magic, but a logical approach to solving problems. Key points:
Break it down into subtasks — find a repeating pattern
Save results — don't count twice
Start with recursion - then optimize
Exercise regularly — DP requires practice
Having mastered dynamic programming, you:
✅ Pass most technical interviews
✅ You will be able to optimize real tasks in production
✅ Understand how the insides of many libraries and frameworks work
✅ Learn to think algorithmically
Remember: Every algorithm once seemed complex even to the best developers. The main thing is practice and patience.
You can learn dynamic programming and many other important topics in Kodik — an educational platform with practical courses for developers. We create content that really helps in interviews and at work!
📱 And we also have a cool Telegram channel with a friendly community where:
Let's analyze the tasks from the interviews
We share useful articles
We help each other grow
Discussing the latest trends in development
Join the community of developers who grow together! 💪