Mastering Dynamic Programming: Detailed Guide with 7 Essential Problems and Solutions

· 7 min read

Hey everyone, it’s alanturrr1703 back again! 😄 Today, we are diving deep into the world of Dynamic Programming (DP), a vital technique in problem-solving, especially in competitive programming and complex real-world applications. If you’ve been struggling with DP or want to sharpen your skills, this 20-minute read will help you understand and solve DP problems step by step.

We’ll cover seven essential DP problems including:

  1. Fibonacci Sequence
  2. 0/1 Knapsack Problem
  3. Longest Common Subsequence (LCS)
  4. Shortest Paths in Graphs (Bellman-Ford and Floyd-Warshall)
  5. Matrix Chain Multiplication
  6. Traveling Salesman Problem (TSP)
  7. Edit Distance

For each problem, we’ll explore both top-down (memoization) and bottom-up (tabulation) approaches with detailed explanations and pseudocode.

Let’s jump in! 🚀

1. Fibonacci Sequence (Classic Problem)

Problem Statement:

Find the n-th Fibonacci number, where the sequence is defined as:

  • Fib(0) = 0
  • Fib(1) = 1
  • Fib(n) = Fib(n-1) + Fib(n-2) for n ≥ 2

Top-Down Approach (Memoization):

In the top-down approach, we break the problem into subproblems recursively and store results in a memoization table to avoid recomputing the same values.

Function Fibonacci(n):
    memo = array of size n + 1 initialized to -1

    Function Fib(n):
        If n == 0:
            Return 0
        ElseIf n == 1:
            Return 1
        If memo[n] != -1:
            Return memo[n]
        memo[n] = Fib(n-1) + Fib(n-2)
        Return memo[n]
    
    Return Fib(n)

Bottom-Up Approach (Tabulation):

In the bottom-up approach, we iteratively calculate Fibonacci numbers from the smallest subproblem up to n.

Function FibonacciDP(n):
    If n == 0:
        Return 0
    If n == 1:
        Return 1

    dp = array of size n + 1
    dp[0] = 0
    dp[1] = 1

    For i = 2 to n:
        dp[i] = dp[i-1] + dp[i-2]

    Return dp[n]

Time Complexity:

  • Time Complexity: O(n)
  • Space Complexity: O(n)

2. 0/1 Knapsack Problem

Problem Statement:

Given n items, each with a weight and a value, and a knapsack with capacity W, find the maximum value that can be obtained without exceeding the weight limit.

Top-Down Approach (Memoization):

Function Knapsack(W, weights, values, n):
    memo = 2D array of size (n + 1) x (W + 1) initialized to -1

    Function DP(i, W):
        If i == 0 or W == 0:
            Return 0
        If memo[i][W] != -1:
            Return memo[i][W]
        If weights[i-1] > W:
            memo[i][W] = DP(i-1, W)
        Else:
            memo[i][W] = max(values[i-1] + DP(i-1, W - weights[i-1]), DP(i-1, W))
        Return memo[i][W]
    
    Return DP(n, W)

Bottom-Up Approach (Tabulation):

Function KnapsackDP(W, weights, values, n):
    dp = 2D array of size (n + 1) x (W + 1)

    For i = 0 to n:
        For w = 0 to W:
            If i == 0 or w == 0:
                dp[i][w] = 0
            ElseIf weights[i-1] <= w:
                dp[i][w] = max(values[i-1] + dp[i-1][w - weights[i-1]], dp[i-1][w])
            Else:
                dp[i][w] = dp[i-1][w]

    Return dp[n][W]

Time Complexity:

  • Time Complexity: O(n * W)
  • Space Complexity: O(n * W)

3. Longest Common Subsequence (LCS)

Problem Statement:

Given two strings X and Y, find the length of the longest subsequence that is present in both strings.

Top-Down Approach (Memoization):

Function LCS(X, Y, m, n):
    memo = 2D array of size (m + 1) x (n + 1) initialized to -1

    Function DP(i, j):
        If i == 0 or j == 0:
            Return 0
        If memo[i][j] != -1:
            Return memo[i][j]
        If X[i-1] == Y[j-1]:
            memo[i][j] = 1 + DP(i-1, j-1)
        Else:
            memo[i][j] = max(DP(i-1, j), DP(i, j-1))
        Return memo[i][j]

    Return DP(m, n)

Bottom-Up Approach (Tabulation):

Function LCSDP(X, Y, m, n):
    dp = 2D array of size (m + 1) x (n + 1)

    For i = 0 to m:
        For j = 0 to n:
            If i == 0 or j == 0:
                dp[i][j] = 0
            ElseIf X[i-1] == Y[j-1]:
                dp[i][j] = 1 + dp[i-1][j-1]
            Else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    Return dp[m][n]

Time Complexity:

  • Time Complexity: O(m * n)
  • Space Complexity: O(m * n)

4. Shortest Paths in Graphs

Problem 1: Bellman-Ford Algorithm

Problem Statement:

Find the shortest path from a source vertex to all other vertices in a graph with possible negative weight edges.

Bellman-Ford Algorithm (Bottom-Up):

Function BellmanFord(vertices, edges, source):
    dist = array of size vertices initialized to infinity
    dist[source] = 0

    For i = 1 to vertices - 1:
        For each edge (u, v, weight):
            If dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight

    # Check for negative-weight cycles
    For each edge (u, v, weight):
        If dist[u] + weight < dist[v]:
            Print "Negative weight cycle detected"
            Return

    Return dist

Time Complexity:

  • Time Complexity: O(vertices * edges)
  • Space Complexity: O(vertices)

Problem 2: Floyd-Warshall Algorithm

Problem Statement:

Find the shortest path between all pairs of vertices in a graph.

Floyd-Warshall Algorithm:

Function FloydWarshall(graph, vertices):
    dist = 2D array of size (vertices x vertices) initialized to infinity

    For i = 0 to vertices - 1:
        dist[i][i] = 0

    For each edge (u, v, weight):
        dist[u][v] = weight

    For k = 0 to vertices - 1:
        For i = 0 to vertices - 1:
            For j = 0 to vertices - 1:
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    Return dist

Time Complexity:

  • Time Complexity: O(vertices³)
  • Space Complexity: O(vertices²)

5. Matrix Chain Multiplication

Problem Statement:

Given a sequence of matrices, find the most efficient way to multiply these matrices together, minimizing the number of scalar multiplications.

Top-Down Approach (Memoization):

Function MatrixChainOrder(p, i, j):
    memo = 2D array of size (n x n) initialized to -1

    Function DP(i, j):
        If i == j:
            Return 0
        If memo[i][j] != -1:
            Return memo[i][j]
        memo[i][j] = infinity
        For k = i to j-1:
            cost = DP(i, k) + DP(k+1, j) + p[i-1] * p[k] * p[j]
            memo[i][j] = min(memo[i][j], cost)
        Return memo[i][j]

    Return DP(1, length(p) - 1)

Bottom-Up Approach (Tabulation):

Function MatrixChainOrderDP(p, n):
    dp = 2D array of size (n x n

)

    For i = 1 to n:
        dp[i][i] = 0

    For length = 2 to n:
        For i = 1 to n - length + 1:
            j = i + length - 1
            dp[i][j] = infinity
            For k = i to j-1:
                cost = dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j]
                dp[i][j] = min(dp[i][j], cost)

    Return dp[1][n-1]

Time Complexity:

  • Time Complexity: O(n³)
  • Space Complexity: O(n²)

6. Traveling Salesman Problem (TSP)

Problem Statement:

Given a set of cities and distances between every pair of cities, find the shortest possible route that visits every city exactly once and returns to the starting point.

Top-Down Approach (Memoization with Bitmasking):

Function TSP(mask, pos):
    If mask == allVisited:
        Return distance[pos][0]

    If dp[mask][pos] != -1:
        Return dp[mask][pos]

    ans = infinity
    For city = 0 to n-1:
        If city is not visited:
            newAns = distance[pos][city] + TSP(mask | (1 << city), city)
            ans = min(ans, newAns)

    dp[mask][pos] = ans
    Return dp[mask][pos]

Time Complexity:

  • Time Complexity: O(n² * 2^n)
  • Space Complexity: O(n * 2^n)

7. Edit Distance (Levenshtein Distance)

Problem Statement:

Given two strings X and Y, find the minimum number of operations (insert, delete, replace) required to convert X into Y.

Top-Down Approach (Memoization):

Function EditDistance(X, Y, m, n):
    memo = 2D array of size (m+1) x (n+1) initialized to -1

    Function DP(i, j):
        If i == 0:
            Return j
        If j == 0:
            Return i
        If memo[i][j] != -1:
            Return memo[i][j]
        If X[i-1] == Y[j-1]:
            memo[i][j] = DP(i-1, j-1)
        Else:
            memo[i][j] = 1 + min(DP(i-1, j), DP(i, j-1), DP(i-1, j-1))
        Return memo[i][j]

    Return DP(m, n)

Bottom-Up Approach (Tabulation):

Function EditDistanceDP(X, Y, m, n):
    dp = 2D array of size (m+1) x (n+1)

    For i = 0 to m:
        For j = 0 to n:
            If i == 0:
                dp[i][j] = j
            ElseIf j == 0:
                dp[i][j] = i
            ElseIf X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1]
            Else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

    Return dp[m][n]

Time Complexity:

  • Time Complexity: O(m * n)
  • Space Complexity: O(m * n)

Conclusion:

In this comprehensive guide, we covered seven essential dynamic programming problems, showing both top-down (memoization) and bottom-up (tabulation) approaches with pseudocode. Mastering these problems will give you the tools to solve a wide range of optimization and combinatorial problems.

The key to dynamic programming lies in understanding the overlapping subproblems and the optimal substructure of the problem. With practice, you’ll be able to recognize DP patterns and apply these techniques to more complex problems.

That’s all for today! I hope this blog helped you understand dynamic programming more deeply. Until next time, happy coding! 🚀