On this page & study actions
Assessed progress
Sign in and complete the verified MCQs to track mastery.
Unit 5: Algorithm Design5 min read
Dynamic Programming (DP) is a powerful algorithmic paradigm used to solve complex problems by breaking them down into simpler, overlapping subproblems. It optimizes solutions by storing the results of these subproblems to avoid redundant computations, ultimately leading to efficient solutions for problems exhibiting specific structural properties.
Dynamic programming is an algorithmic technique for solving optimization problems. It is applicable when a problem's solution can be expressed as a sequence of decisions, and these decisions exhibit two key properties: optimal substructure and overlapping subproblems.
The general method involves building up solutions from smaller subproblems to larger ones, either in a bottom-up (tabulation) or top-down (memoization) fashion.
Steps in Dynamic Programming:
A multistage graph is a directed graph where vertices are partitioned into disjoint sets . Edges only exist between vertices in adjacent sets, i.e., if is an edge, then and for some . The problem is to find a minimum-cost path from a source to a sink .
Let be the cost of the edge .
Forward Approach (Backward Recurrence): Let be the minimum cost path from node in stage to the sink node . The recurrence relation is: The base case is for nodes in the last stage , where .
Backward Approach (Forward Recurrence): Let be the minimum cost path from the source node to node in stage . The recurrence relation is: The base case is for the source node , where .
Consider the following multistage graph:
(1) --9--> (2) --4--> (6) --6--> (9) --4--> (12)
| / \ / \ / \ |
| 7 2 / 5 / \ |
| / \ / \ / \ |
3 / \ / \ / \ |
| / \ / X \ |
| (3) --2--> (7) --4--> (10) --2--> (12)
| / / \ / \ |
| 7 / 3 / \ |
| / / \ / \ |
(4) --11--> (8) --5--> (11) --5--> (12)
| / \ / \ |
| 2 1 6 3 |
| / \ / \ |
2 / \ / \ |
| / \ / \ |
(5) --11--> (7) ----------> (10) -----
\ 8 \
\ \
---------> (8)(Edges with multiple costs from a single source to different destinations or within the diagram are corrected for clarity. Each distinct line segment represents an edge with a single cost.)
Let's use the Forward Approach (Backward Recurrence) for a simplified path calculation:
We want to find . , , , , .
Stage 4 (nodes 9, 10, 11):
Stage 3 (nodes 6, 7, 8): (path via 10) (path via 10) (path via 10)
Stage 2 (nodes 2, 3, 4, 5): (path via 7) (path via 6) (path via 8) (path via 8)
Stage 1 (node 1): (path via 2 or 3)
The minimum cost path from source 1 to sink 12 is 16. An optimal path could be or .
The 0-1 Knapsack Problem involves selecting items, each with a specific weight and profit, to fit into a knapsack with a maximum capacity . The objective is to maximize the total profit of selected items, with the constraint that the total weight does not exceed . The "0-1" signifies that each item is indivisible; you can either take the entire item (1) or leave it completely (0). This problem cannot be solved optimally using a greedy approach because a locally optimal choice (e.g., picking the item with the highest profit-to-weight ratio) might prevent a globally optimal solution.
Problem Statement: Given items, where item has weight and profit , and a knapsack of capacity . Choose a subset of items such that their total weight is at most , and their total profit is maximized.
Dynamic Programming Formulation: Let represent the maximum profit that can be obtained from the first items with a knapsack capacity of .
The recurrence relation is:
0 & \text{if } i=0 \text{ or } j=0 \\ dp[i-1][j] & \text{if } w_i > j \\ \max(dp[i-1][j], p_i + dp[i-1][j-w_i]) & \text{if } w_i \le j \end{cases}$$ Here, $w_i$ and $p_i$ refer to the weight and profit of the $i$-th item (using 1-based indexing for items in the DP table). * **Base cases:** If there are no items ($i=0$) or no capacity ($j=0$), the profit is $0$. * **If $w_i > j$**: The current item is too heavy for the remaining capacity $j$, so we cannot include it. The maximum profit is the same as considering the first $i-1$ items with capacity $j$. * **If $w_i \le j$**: We have two choices: 1. **Exclude the $i$-th item**: The profit is $dp[i-1][j]$. 2. **Include the $i$-th item**: The profit is $p_i$ plus the maximum profit from the first $i-1$ items with the remaining capacity $j - w_i$. We take the maximum of these two choices. The final answer will be $dp[n][W]$. **C++ Code Example (Bottom-Up Tabulation):** ```cpp #include <iostream> #include <vector> #include <algorithm> // For std::max // Function to solve the 0-1 Knapsack problem using dynamic programming int knapsack01(int W, const std::vector<int>& weights, const std::vector<int>& profits, int n) { // dp[i][j] will store the maximum profit that can be obtained // using the first 'i' items with a knapsack capacity of 'j'. std::vector<std::vector<int>> dp(n + 1, std::vector<int>(W + 1, 0)); // Build the dp table in a bottom-up manner for (int i = 1; i <= n; ++i) { for (int j = 1; j <= W; ++j) { // Get weight and profit of the current item (i-1 because vectors are 0-indexed) int currentWeight = weights[i - 1]; int currentProfit = profits[i - 1]; // If the current item's weight is greater than the current capacity 'j', // we cannot include this item. // So, the maximum profit remains the same as without this item. if (currentWeight > j) { dp[i][j] = dp[i - 1][j]; } else { // We have two choices: // 1. Exclude the current item: dp[i-1][j] // 2. Include the current item: currentProfit + dp[i-1][j - currentWeight] // (The profit of the current item plus the max profit from previous items // with the remaining capacity) dp[i][j] = std::max(dp[i - 1][j], currentProfit + dp[i - 1][j - currentWeight]); } } } // The maximum profit for 'n' items and capacity 'W' is stored in dp[n][W] return dp[n][W]; } int main() { std::vector<int> profits = {60, 100, 120}; std::vector<int> weights = {10, 20, 30}; int W = 50; // Knapsack capacity int n = profits.size(); // Number of items std::cout << "Items: \n"; for (int i = 0; i < n; ++i) { std::cout << " Item " << i + 1 << ": Weight = " << weights[i] << ", Profit = " << profits[i] << std::endl; } std::cout << "Knapsack Capacity: " << W << std::endl; int maxProfit = knapsack01(W, weights, profits, n); std::cout << "Maximum profit for 0-1 Knapsack: " << maxProfit << std::endl; // Expected: 220 (item 2 (100) + item 3 (120)) // Another example profits = {25, 24, 15}; weights = {18, 15, 10}; W = 20; n = profits.size(); std::cout << "\nItems: \n"; for (int i = 0; i < n; ++i) { std::cout << " Item " << i + 1 << ": Weight = " << weights[i] << ", Profit = " << profits[i] << std::endl; } std::cout << "Knapsack Capacity: " << W << std::endl; maxProfit = knapsack01(W, weights, profits, n); std::cout << "Maximum profit for 0-1 Knapsack: " << maxProfit << std::endl; // Expected: 24 (only item 2, item 1 is too heavy, item 3 + item 1 is too heavy) return 0; } ``` ## 4. Traveling Salesperson Problem (TSP) with Dynamic Programming The **Traveling Salesperson Problem (TSP)** is a classic NP-hard optimization problem. Given a list of cities and the distances between each pair of cities, the problem is to find the shortest possible route that visits each city exactly once and returns to the origin city. This route is known as a **Hamiltonian cycle**. While NP-hard in general, dynamic programming can solve TSP for a smaller number of cities (typically up to 20-25) more efficiently than brute-force. The common DP approach for TSP is the **Held-Karp algorithm**. **Problem Statement:** Given a set of $n$ cities and a cost matrix $C$ where $C_{ij}$ is the cost of traveling from city $i$ to city $j$. Find a permutation of cities $(c_1, c_2, \dots, c_n)$ that minimizes the total cost $C_{c_1 c_2} + C_{c_2 c_3} + \dots + C_{c_n c_1}$. **Dynamic Programming Formulation (Held-Karp):** Let $g(i, S)$ be the minimum cost to start at city $i$, visit all cities in the set $S$ exactly once, and then return to the starting city (let's assume city 1 is the fixed starting/ending city). The state $S$ is a subset of cities, *excluding* the starting city (city 1) and *excluding* city $i$. The recurrence relation is: $$g(i, S) = \min_{j \in S} \{ C_{ij} + g(j, S - \{j\}) \}$$ **Base Case:** When $S$ is an empty set (meaning all intermediate cities have been visited), we must return to the starting city (city 1). $$g(i, \emptyset) = C_{i1}$$ The final solution is $g(1, V - \{1\})$, where $V$ is the set of all cities. Let's illustrate with a small example: $n=4$ cities. Start and end at city 1. Cities are $\{1, 2, 3, 4\}$. Cost matrix: ```text To: 1 2 3 4 From: 1 0 9 7 3 2 9 0 2 4 3 7 2 0 3 4 3 4 3 0 ``` We want to find $g(1, \{2, 3, 4\})$. **Step 1: Base Cases (S is empty)** $g(2, \emptyset) = C_{21} = 9$ $g(3, \emptyset) = C_{31} = 7$ $g(4, \emptyset) = C_{41} = 3$ **Step 2: Subsets of size 1** $S = \{k\}$ $g(i, \{k\}) = C_{ik} + g(k, \emptyset)$ $g(2, \{3\}) = C_{23} + g(3, \emptyset) = 2 + 7 = 9$ $g(2, \{4\}) = C_{24} + g(4, \emptyset) = 4 + 3 = 7$ $g(3, \{2\}) = C_{32} + g(2, \emptyset) = 2 + 9 = 11$ $g(3, \{4\}) = C_{34} + g(4, \emptyset) = 3 + 3 = 6$ $g(4, \{2\}) = C_{42} + g(2, \emptyset) = 4 + 9 = 13$ $g(4, \{3\}) = C_{43} + g(3, \emptyset) = 3 + 7 = 10$ **Step 3: Subsets of size 2** $S = \{k_1, k_2\}$ $g(i, \{k_1, k_2\}) = \min \{ C_{ik_1} + g(k_1, \{k_2\}), C_{ik_2} + g(k_2, \{k_1\}) \}$ $g(2, \{3, 4\}) = \min \{ C_{23} + g(3, \{4\}), C_{24} + g(4, \{3\}) \}$ $= \min \{ 2 + 6, 4 + 10 \} = \min \{ 8, 14 \} = 8$ (via city 3) $g(3, \{2, 4\}) = \min \{ C_{32} + g(2, \{4\}), C_{34} + g(4, \{2\}) \}$ $= \min \{ 2 + 7, 3 + 13 \} = \min \{ 9, 16 \} = 9$ (via city 2) $g(4, \{2, 3\}) = \min \{ C_{42} + g(2, \{3\}), C_{43} + g(3, \{2\}) \}$ $= \min \{ 4 + 9, 3 + 11 \} = \min \{ 13, 14 \} = 13$ (via city 2) **Step 4: Final Step (Subset of size 3)** $S = \{2, 3, 4\}$ $g(1, \{2, 3, 4\}) = \min \{ C_{12} + g(2, \{3, 4\}), C_{13} + g(3, \{2, 4\}), C_{14} + g(4, \{2, 3\}) \}$ $= \min \{ 9 + 8, 7 + 9, 3 + 13 \}$ $= \min \{ 17, 16, 16 \} = 16$ (via city 3 or city 4) The minimum cost tour starting and ending at city 1 is 16. To reconstruct the path: If $g(1, \{2,3,4\}) = 16$ was achieved via $C_{13} + g(3, \{2,4\})$, then the path starts $1 \to 3$. Next, $g(3, \{2,4\}) = 9$ was achieved via $C_{32} + g(2, \{4\})$, so the path continues $1 \to 3 \to 2$. Next, $g(2, \{4\}) = 7$ was achieved via $C_{24} + g(4, \emptyset)$, so the path continues $1 \to 3 \to 2 \to 4$. Finally, $g(4, \emptyset) = C_{41} = 3$, returning to city 1. Optimal tour: $1 \to 3 \to 2 \to 4 \to 1$ with total cost $C_{13} + C_{32} + C_{24} + C_{41} = 7 + 2 + 4 + 3 = 16$. ## 5. Optimal Binary Search Trees (OBST) An **Optimal Binary Search Tree (OBST)** is a binary search tree constructed for a given set of sorted keys ($k_1 < k_2 < \dots < k_n$) and their associated search probabilities ($p_1, p_2, \dots, p_n$). Additionally, we consider probabilities of searching for values not present in the tree, which fall between keys or outside the range. These are represented by **dummy keys** $d_0, d_1, \dots, d_n$, with search probabilities $q_0, q_1, \dots, q_n$. The objective is to construct a BST that minimizes the **expected search cost**. **Problem Statement:** Given $n$ sorted keys $K = \{k_1, k_2, \dots, k_n\}$ with search probabilities $P = \{p_1, p_2, \dots, p_n\}$ and $n+1$ dummy keys $D = \{d_0, d_1, \dots, d_n\}$ representing unsuccessful searches, with probabilities $Q = \{q_0, q_1, \dots, q_n\}$. Construct a binary search tree for these keys such that the expected search cost is minimized. The expected search cost is calculated as $\sum_{i=1}^{n} (\text{depth}(k_i) + 1) \cdot p_i + \sum_{j=0}^{n} (\text{depth}(d_j) + 1) \cdot q_j$. **Example Binary Search Trees for keys {3, 7, 9, 12}:** ```text (a) (b) (c) (d) 9 7 3 12 / \ / \ \ / 3 12 3 9 7 3 \ / \ \ \ 7 . 12 9 7 \ 12 ``` Different arrangements lead to different search costs. The goal of OBST is to find the arrangement that yields the minimum expected cost. **Dynamic Programming Formulation:** Let $C(i, j)$ be the minimum expected search cost for the subtree containing keys $k_i, \dots, k_j$ and dummy keys $d_{i-1}, \dots, d_j$. Let $W(i, j)$ be the sum of probabilities for keys $k_i, \dots, k_j$ and dummy keys $d_{i-1}, \dots, d_j$. $$W(i, j) = \sum_{l=i}^{j} p_l + \sum_{l=i-1}^{j} q_l$$ For $j < i-1$, $W(i, j) = 0$. For $j=i-1$, $W(i, i-1) = q_{i-1}$. If $k_r$ is chosen as the root of the subtree containing keys $k_i, \dots, k_j$: * The left subtree will contain keys $k_i, \dots, k_{r-1}$ and dummy keys $d_{i-1}, \dots, d_{r-1}$. Its cost is $C(i, r-1)$. * The right subtree will contain keys $k_{r+1}, \dots, k_j$ and dummy keys $d_r, \dots, d_j$. Its cost is $C(r+1, j)$. * All nodes in these subtrees will have their depth increased by 1 (relative to their original root $k_r$), so their total probability sum $W(i, j)$ is added. The recurrence relation is: $$C(i, j) = W(i, j) + \min_{i \le r \le j} \{C(i, r-1) + C(r+1, j)\}$$ **Base Cases:** * $C(i, i-1) = W(i, i-1) = q_{i-1}$ (cost of dummy node representing unsuccessful search between $k_{i-1}$ and $k_i$) * $C(i, i) = W(i, i) + \min_{i \le r \le i} \{C(i, r-1) + C(r+1, i)\} = W(i,i) + C(i,i-1) + C(i+1,i) = p_i + q_{i-1} + q_i$ The final answer will be $C(1, n)$. This DP approach systematically builds up optimal subtrees of increasing size to find the overall optimal BST. ## Summary * **Dynamic Programming (DP)** is an algorithmic technique for solving optimization problems by breaking them into **overlapping subproblems** and problems exhibiting **optimal substructure**. * **0-1 Knapsack Problem** seeks to maximize profit by selecting indivisible items within a weight capacity. DP provides an optimal solution by considering two choices for each item: include it or exclude it, using a table $dp[i][j]$ to store maximum profit for $i$ items and capacity $j$. * The **Traveling Salesperson Problem (TSP)** aims to find the shortest Hamiltonian cycle visiting all cities exactly once. For smaller instances, the **Held-Karp dynamic programming algorithm** offers an optimal solution using states $g(i, S)$ representing minimum cost paths from city $i$ through subset $S$ back to the start. * **Optimal Binary Search Trees (OBST)** minimize the expected search cost for a given set of sorted keys and their search probabilities (including dummy keys for unsuccessful searches). DP builds the optimal tree by considering each key as a potential root for subtrees, calculating costs $C(i, j)$ and total probabilities $W(i, j)$.A technique for optimizing recursive solutions by storing results of subproblems to avoid recomputation, applicable to problems with optimal substructure and overlapping subproblems.
A dynamic programming problem where the goal is to select a subset of indivisible items, each with a weight and a profit, to maximize total profit within a knapsack's capacity.
Finding the shortest Hamiltonian cycle in a graph that visits each vertex exactly once and returns to the starting vertex, often solved efficiently for smaller graphs using DP's Held-Karp algorithm.
A dynamic programming problem focused on constructing a binary search tree from a sorted sequence of keys with associated search probabilities, minimizing the expected cost of searching.
Two key properties indicating a problem can be solved with dynamic programming: optimal substructure means an optimal solution contains optimal solutions to its subproblems, and overlapping subproblems means the same subproblems are solved repeatedly.
Test your understanding with 5 questions
Which characteristic is essential for a problem to be efficiently solved using dynamic programming?
In the 0-1 Knapsack Problem, why is dynamic programming preferred over a greedy approach like 'profit per unit weight'?
The Held-Karp algorithm is a dynamic programming approach commonly used for which problem?
When constructing an Optimal Binary Search Tree using dynamic programming, what is the primary objective?
What does $DP[i][w]$ typically represent in a dynamic programming solution for the 0-1 Knapsack Problem?
6 Modules
6 Modules