Introduction to Dynamic Programming (DP)

Dynamic Programming (DP) is an optimization technique used for solving problems that can be divided into smaller, overlapping subproblems and exhibit optimal substructure. This lesson combines theory, state visualization, and interactive examples to help students easily understand the core concepts of DP.

1. Overlapping Subproblems and Optimal Substructure

Every problem solved using DP satisfies two key properties:

Optimal substructure: the optimal solution to the entire problem can be formed from optimal solutions to its subproblems.
Overlapping subproblems: the same subproblems appear multiple times; storing results prevents redundant computations.

Visual example: Fibonacci sequence


// Fib(5) recursively:
// fib(5)
// ├─ fib(4)
// │  ├─ fib(3)
// │  │  ├─ fib(2)
// │  │  └─ fib(1)
// │  └─ fib(2) <- repeated
// └─ fib(3) <- repeated

Note: memoization prevents multiple computations of the same nodes in the recursion tree.

2. Top-down (Memoization) vs Bottom-up (Tabulation)

Top-down: recursion + storing subproblem results in an array or hash map.


int fib(int n, vector& memo) {
    if(n <= 1) return n;
    if(memo[n] != -1) return memo[n];
    memo[n] = fib(n-1, memo) + fib(n-2, memo);
    return memo[n];
}

Bottom-up: iteratively builds solutions from the smallest subproblems upward, with no recursion.


int fibTab(int n) {
    vector dp(n+1);
    dp[0] = 0; dp[1] = 1;
    for(int i=2; i<=n; ++i)
        dp[i] = dp[i-1] + dp[i-2];
    return dp[n];
}

Tabulation visualization: dp array = [0, 1, 1, 2, 3, 5]

3. Simple Practice Examples

3.1 Number of Ways to Climb Stairs


// DP array dp[i] = number of ways to reach the i-th step
dp[0] = 1;
dp[1] = 1;
for i = 2 to N:
    dp[i] = dp[i-1] + dp[i-2];

Visualization for N = 5: dp = [1, 1, 2, 3, 5, 8]

3.2 Maximum Subarray Sum


// dp[i] = maximum subarray sum ending at index i
dp[0] = nums[0];
for i = 1 to n-1:
    dp[i] = max(nums[i], dp[i-1] + nums[i]);
maxSum = max(dp[0..n-1]);

Visualization: nums = [3, -1, 4, -2, 5] → dp = [3, 2, 6, 4, 9]

4. Suggested Exercises (Interactive)

Compute the number of ways to climb 10 steps using memoization and tabulation.
Find the maximum subarray sum of {3, -1, 4, -2, 5}.
Write a DP function for the minimum number of coins needed to reach a given amount (Coin Change problem).
Print or visualize the dp array at each step of the algorithm (using console output or logs).

5. Additional Resources

Lesson page: /uvod_u_dp.html

Dynamic Programming Examples — National Competition Level

This section presents two typical DP problems suitable for 8th grade or the first year of high school. Each example includes step-by-step explanation, the DP array, and a full C++ implementation.

Example 1 — Number of Ways to Climb Stairs (Staircase Problem)

Task: You are given N steps. At each move, you may climb 1 or 2 steps. Compute the number of different ways to reach the top.

Problem analysis:

To reach step i, you can come from step i-1 or step i-2.
Overlapping subproblems: the results for (i-1) and (i-2) are reused.
Optimal substructure: the solution for step i depends only on the previous two solutions.


#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N;
    cout << "Enter number of steps: ";
    cin >> N;

    if(N == 0) { cout << 0; return 0; }

    vector<int> dp(N+1);
    dp[0] = 1;  // 1 way to stay on the ground
    dp[1] = 1;  // 1 way to climb the first step

    for(int i = 2; i <= N; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }

    cout << "Number of ways: " << dp[N] << endl;
    return 0;
}

Explanation:
– dp[i] stores the number of ways to reach step i.
– Base cases: dp[0] = 1, dp[1] = 1.
– Recurrence: dp[i] = dp[i-1] + dp[i-2].
– The final answer is dp[N].

Example 2 — Maximum Subarray Sum

Task: Given an array of integers, find the sum of the largest continuous subarray.

Problem analysis:

dp[i] = maximum subarray sum ending at index i.
Optimal substructure: dp[i] depends only on dp[i-1] and the current element.
Overlapping subproblems: each step uses the previous result dp[i-1].


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {3, -1, 4, -2, 5};
    int n = nums.size();

    vector<int> dp(n);
    dp[0] = nums[0];
    int maxSum = dp[0];

    for(int i = 1; i < n; i++) {
        dp[i] = max(nums[i], dp[i-1] + nums[i]);
        maxSum = max(maxSum, dp[i]);
    }

    cout << "Maximum subarray sum: " << maxSum << endl;
    return 0;
}

Explanation:
– For the first element: dp[0] = nums[0].
– For each next element: dp[i] = max(nums[i], dp[i-1] + nums[i]) — choose whether to start a new subarray or extend the previous one.
– The maximum value in dp is the final answer.

These examples cover fundamental DP patterns: counting paths (overlapping subproblems + optimal substructure) and iterative tabulation (Kadane's algorithm). Such problems frequently appear in national-level programming competitions and introduce students to more advanced DP tasks.

Example 3 — Number of Ways to Form a Sum (Coin Change)

Task: You are given a list of coin denominations and a target sum S. Find how many different ways you can form the sum S using the coins. Each coin may be used multiple times.

Problem Analysis:

Overlapping subproblems: the number of ways to form S depends on the number of ways to form smaller sums.
Optimal substructure: for each sum, we can add a coin and combine previously computed results.
The DP array dp[i] stores the number of ways to form the sum i.


#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, S;
    cout << "Enter the number of coin types: ";
    cin >> n;

    vector<int> coins(n);
    cout << "Enter the coin values: ";
    for(int i = 0; i < n; i++) cin >> coins[i];

    cout << "Enter the target sum: ";
    cin >> S;

    vector<int> dp(S+1, 0);
    dp[0] = 1;  // There is exactly 1 way to form the sum 0

    for(int i = 0; i < n; i++) {
        for(int s = coins[i]; s <= S; s++) {
            dp[s] += dp[s - coins[i]];
        }
    }

    cout << "Number of ways to form sum " << S << ": " << dp[S] << endl;
    return 0;
}

Explanation:

dp[0] = 1 because there is exactly one way to select no coins.
For each coin value coins[i], we iterate through all sums from coins[i] to S.
For a given sum s, we add dp[s - coins[i]] because using this coin extends all valid combinations that form the smaller sum.
Finally, dp[S] contains the total number of combinations that form the sum S.

This problem introduces students to **multi-step DP** and **combinatorial DP**, which commonly appears in national-level programming competitions.

Limitations of Dynamic Programming (DP)

Dynamic programming is a powerful technique for solving optimization and combinatorial problems, but it is not a universal solution. There are situations where DP is not applicable or can be inefficient. Below are the key limitations of DP that students should understand.

No overlapping subproblems – If subproblems do not repeat (as in a "divide and conquer" approach), DP provides no savings; often classical recursion or another algorithm is faster.
No optimal substructure – DP relies on the ability to construct the optimal solution from optimal solutions of subproblems. If this does not hold (e.g., problems where local optima lead to globally poor solutions), DP will fail.
High memory consumption – DP tables can contain thousands or millions of states. For problems with two or more dimensions, memory usage can grow exponentially (e.g., DP[n][sum]).
Too many states – If the number of states is enormous (e.g., hundreds of thousands or more), runtime becomes impractical, even if each step is O(1).
Difficulty defining states – For some problems, it is hard to define clear DP states or transitions between them. Often, even formulating a DP solution can be more complex than solving the problem directly.
Inefficient for problems with continuous values – DP usually works over discrete states. If the problem involves real numbers, the range can be infinite and DP becomes impractical.
Complex transitions – If transitions between states are expensive (e.g., each state requires iterating over 1000 others), the DP formula becomes slow and unfeasible.

Understanding these limitations helps students recognize when DP is the right solution, and when other techniques such as heuristics, greedy algorithms, graph algorithms, or recursive "divide and conquer" approaches should be used.

DP vs. Greedy vs. Divide & Conquer

A brief overview of the key differences between these three essential algorithmic problem-solving techniques. The table helps students choose the right approach depending on the problem's structure.

Technique	When to Use	Advantages	Disadvantages	Example Problems
Dynamic Programming (DP)	Problems with overlapping subproblems and optimal substructure.	– produces optimal solutions – good for combinatorial problems – solves complex tasks like scheduling and paths	– can require large memory – states can be hard to define – slower than greedy methods	Fibonacci, Knapsack, LCS, shortest paths (DAG)
Greedy Algorithms	Problems where a local optimum leads to a globally optimal solution.	– very fast (often O(n log n) or better) – simple to implement – good approximation when optimal is not possible	– do not always guarantee optimality – require a specific problem structure	Kruskal, Prim, Huffman, Activity Selection
Divide & Conquer	Problems that can be split into independent subproblems.	– efficiently solves large problems – leverages parallelism – often very elegant solutions	– not helpful if subproblems overlap (DP is better then) – recursion can sometimes be complex	MergeSort, QuickSort, Binary Search, FFT

Time and Space Complexity in Dynamic Programming

Dynamic programming allows significant acceleration of algorithms, but often comes with increased memory usage. Understanding complexity and optimization techniques is key for applying DP to real-world problems.

Time Complexity

The time complexity of DP algorithms is usually proportional to the number of states and the number of transitions between them. In common applications, the complexity is:

O(n) — simple linear DP (e.g., iterative Fibonacci)
O(n · k) — problems where each state has a limited number of transitions
O(n²) or more — typical for segment, interval, or matrix problems

Space Complexity

The space complexity of DP depends on the size of the DP table. Often:

O(n) — optimized linear DP models
O(n · k) — combinatorial and knapsack variants
O(n²) — interval DP or 2D subproblems

Tips for Optimizing DP Algorithms

1. Iterative Tabulation Instead of Recursive Memoization

When possible, use an iterative bottom-up implementation. It is faster, more efficient, and avoids issues such as stack overflow.

2. Space Optimization

In many DP models, the entire table is not needed — often only the last one or two rows are sufficient. Typical examples:

Fibonacci — from O(n) to O(1)
Knapsack — reduce 2D table to 1D array
LCS/LIS — partial memory reduction

3. Testing with Large Inputs

Before applying DP solutions in contests or real-world datasets, check:

whether the DP table fits in memory (especially for 2D matrices)
how many transitions exist per state
whether modular arithmetic is needed for large numbers

4. Identifying Unnecessary States

Often, the DP table contains more states than actually needed. Before reducing memory, identify which states are truly reachable or useful.

5. State Compression and Transition Optimization

For more complex problems (e.g., DP on bitmasks), memory can be reduced by encoding states with fewer bits or using more efficient data structures.

Understanding these principles allows dynamic programming to be applied to very large problems without slowing down the program or consuming excessive memory.

Recommended Resources for Learning Dynamic Programming

For a deeper understanding of DP techniques, it is useful to learn from different formats: textual tutorials, video lectures, and interactive platforms. Below are carefully selected quality resources covering both basic and advanced topics.

Textual Tutorials and Articles

CP-Algorithms — Dynamic Programming — one of the clearest and most popular explanations of DP techniques.
GeeksForGeeks — Dynamic Programming — a large number of practical examples and solved problems.
LeetCode Learn — DP Card — a guide through basic and medium-level DP problems.

Video Lectures

WilliamFiset — Dynamic Programming Playlist — clear explanations with visualizations.
MIT OpenCourseWare — DP Intro — university lecture with examples.
Errichto — DP for Competitive Programming — focused on competitive programming.

□ Interactive Platforms

USACO Guide — Interactive DP Lessons — interactive exercises with explanations.
HackerRank DP Challenges — progressively arranged exercises for practice.
Codeforces — DP Problems — a large selection of problems of varying difficulty.

Recommended Books

Introduction to Algorithms (CLRS) — the most famous university textbook, covering DP in detail.
The Algorithm Design Manual — Skiena — a practical approach to problem-solving, including DP methods.
Algorithm Design — Kleinberg & Tardos — an excellent book for intuitive understanding of techniques, including DP.

Exploring these resources will help students expand their knowledge of dynamic programming and gain confidence in solving a variety of problems.

Introduction to Dynamic Programming (DP)

1. Overlapping Subproblems and Optimal Substructure

2. Top-down (Memoization) vs Bottom-up (Tabulation)

3. Simple Practice Examples

3.1 Number of Ways to Climb Stairs

3.2 Maximum Subarray Sum

4. Suggested Exercises (Interactive)

5. Additional Resources

Dynamic Programming Examples — National Competition Level

Example 1 — Number of Ways to Climb Stairs (Staircase Problem)

Example 2 — Maximum Subarray Sum

Example 3 — Number of Ways to Form a Sum (Coin Change)

Limitations of Dynamic Programming (DP)

DP vs. Greedy vs. Divide & Conquer

Time and Space Complexity in Dynamic Programming

Time Complexity

Space Complexity

Tips for Optimizing DP Algorithms

1. Iterative Tabulation Instead of Recursive Memoization

2. Space Optimization

3. Testing with Large Inputs

4. Identifying Unnecessary States

5. State Compression and Transition Optimization

Hidden Mini Quiz — Dynamic Programming (DP)

Mini Quiz: Do you understand the basics of DP?

Mini Exercises for Independent Practice

Recommended Resources for Learning Dynamic Programming

Textual Tutorials and Articles

Video Lectures

□ Interactive Platforms

Recommended Books

Introduction to Dynamic Programming (DP)

1. Overlapping Subproblems and Optimal Substructure

2. Top-down (Memoization) vs Bottom-up (Tabulation)

3. Simple Practice Examples

3.1 Number of Ways to Climb Stairs

3.2 Maximum Subarray Sum

4. Suggested Exercises (Interactive)

5. Additional Resources

Dynamic Programming Examples — National Competition Level

Example 1 — Number of Ways to Climb Stairs (Staircase Problem)

Example 2 — Maximum Subarray Sum

Example 3 — Number of Ways to Form a Sum (Coin Change)

Limitations of Dynamic Programming (DP)

DP vs. Greedy vs. Divide & Conquer

Time and Space Complexity in Dynamic Programming

Time Complexity

Space Complexity

Tips for Optimizing DP Algorithms

1. Iterative Tabulation Instead of Recursive Memoization

2. Space Optimization

3. Testing with Large Inputs

4. Identifying Unnecessary States

5. State Compression and Transition Optimization

Hidden Mini Quiz — Dynamic Programming (DP)

Mini Quiz: Do you understand the basics of DP?

Mini Exercises for Independent Practice

Recommended Resources for Learning Dynamic Programming

Textual Tutorials and Articles

Video Lectures

□ Interactive Platforms

Recommended Books

Cookie settings