Dynamic programming is an algorithmic technique used to optimize solutions to optimization problems with optimal substructure and overlapping subproblems. In this article, we will break the definition down and dive deep into the concept and its implementation.

Optimal Substructure & Overlapping Subproblems

A problem is said to have optimal substructure when its optimal solution is composed of the optimal solutions to its smaller subproblems. If you have been following the blog, you should already be familiar with such problems, like the Fibonacci problem we discussed in the Haskell series. The optimal solution, $fib(n)$, is determined by the optimal solutions of its subproblems, $fib(n-1)$ and $fib(n-2)$. ($fib(n) = fib(n-1) + fib(n-2)$). Many real-world optimization problems, such as shortest path problems, also exhibit optimal substructure. For example, the shortest path from A to C is almost always the shortest path from A to B combined with the shortest path from B to C.

The Fibonacci problem also has overlapping subproblems. For instance, $fib(3)$ is computed as $fib(2) + fib(1)$, which is further broken down into $fib(1) + fib(0) + fib(1)$, containing only base cases. Here, $fib(1)$ appears twice, requiring multiple computations in conventional recursion. Dynamic programming is a technique that addresses this repeated computation to make the algorithm more efficient.

Tabulation & Memorization

The key strategy of dynamic programming is to compute the solutions to the subproblems only once by storing the results as they are computed. There are two approaches to implementing dynamic programming: tabulation and memoization.Memoization is the top-down approach. It stores the solutions to subproblems during recursive calls and reuses them as needed. For example, when encountering $fib(2) + fib(1)$, we can store the result of $fib(1)$ and use it to compute $fib(2)$, which in turn can be used to compute $fib(3)$.

// Memorization
int fibMemo(int n, vector<int> &memo) {
    if (n == 0) {
        return 1;
    }
 
    if (memo[n] != -1) {
        return memo[n];
    }
 
    memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo);
    return memo[n];
};
 
// Tabulation
int fibTable (int n) {
    vector<int> table(n+1);
 
    table[0] = 1;
    table[1] = 1;
 
    for (int i = 2; i <= n; i++) {
        table[i] = table[i-1] + table[i-2];
    }
 
    return table[n];
};

Tabulation is the bottom-up approach. It starts by solving the base cases and iteratively fills up a table until the solution to the original problem is found. For instance, we can compute and store $fib(0)$ and $fib(1)$, then use them to compute $fib(2)$, which is subsequently used to compute $fib(3)$. When there are only a few subproblems that need to be solved, memoization might be more efficient. However, tabulation is generally preferred due to its simplicity, lack of risk of stack overflow, and potential for reduced memory usage. For example, in the Fibonacci problem, we can identify that only the last two solutions are required at any point, allowing us to reduce the memory requirement to storing just two values instead of an array of size $n$. (Exercise Q1)

Framework for Dynamic Programming

To apply dynamic programming effectively, you need to identify the problem, analyze it, and apply the technique correctly. Start by solving the smallest problems to understand the potential base cases and recurrence relation. In the Fibonacci problem, computing $fib(0)$, $fib(1)$, $fib(2)$, and $fib(3)$ reveals that the base cases are $fib(0)$ and $fib(1)$, with the recurrence relation $fib(n) = fib(n-1) + fib(n-2)$. Next, determine what needs to be stored at each iteration (for tabulation) to construct the solution. In the Fibonacci problem, we notice that $fib(0)$ becomes irrelevant for computing $fib(3)$ and subsequent values of $n$, allowing us to reduce storage to only the previous two values.

Bellman-Ford Algorithm

Dijkstra's algorithm has the limitation of not allowing negative edge weights. The Bellman-Ford algorithm overcomes this by applying dynamic programming. It uses the fact that the shortest path from the start to a destination node must not contain a cycle and can be determined by summing the weights of at most $V-1$ edges. By iteratively updating the smallest distances from the start node to all reachable nodes for at most $V-1$ steps, Bellman-Ford examines all possible paths and guarantees the shortest path even with negative edges.

void Bellman_Ford(WeightedAdjacencyMatrix graph, int start, int end) {
    int v = graph.mat.size();
    vector<int> estimates(v, 100);
    estimates[start] = 0;
 
    for (int i = 0; i < v; i++) {
        for (int j = 0; j < v; j++) {
            if (estimates[j] != 100) {
                for (int k = 0; k < v; k++) {
                    if (graph.mat[j][k] != 0) {
                        estimates[k] = min(estimates[k], estimates[j] + graph.mat[j][k]);
                    }
                }
            }
        }
    }
 
    cout << "Min cost is " << estimates[end] << endl;
};

When applied to a weighted adjacency list instead of an adjacency matrix, the time complexity is reduced from $O(V^3)$ to $O(VE)$, as we iterate over all edges $V$ times to update the estimated costs. However, the algorithm cannot handle graphs containing negative cycles, as they allow the cost to reduce indefinitely. The shortest path can be determined by keeping track of the previous node when updating the estimates. (Exercise Q2)

Conclusion

In this article, we discussed the problems dynamic programming addresses, how it works, and its implementation in problems like Fibonacci and shortest path finding. Since dynamic programming is crucial for solving optimization problems, it is highly relevant in fields like machine learning, which we will explore in future articles in the machine learning series.

Exercises

From this article, there will be an exercise section where you can test your understanding of the material introduced in the article. I highly recommend solving these questions by yourself after reading the main part of the article. You can click on each question to see its answer.

Resources

• GeeksForGeeks. 2024. Bellman–Ford Algorithm. GeeksForGeeks.