Mathematics Foundations/19.3 Dynamic Programming

19.3 Dynamic Programming Introduction Dynamic programming (DP) is a mathematical optimization method that breaks down complex problems into simpler subproblems and solves each subproblem only once, storing the solutions to avoid redundant computations. This approach was developed by Richard Bellman in the 1950s and has become fundamental in optimization theory, computer science, and operations research. Mathematical Foundations Dynamic programming is based on the principle of optimality, which states that an optimal solution to a problem contains optimal solutions to its subproblems. Formally, if is an optimal solution to problem P, and if contains a decision leading to subproblem P', then the portion of solving P' must be optimal for P'. The Bellman equation, a cornerstone of dynamic programming, can be expressed as: where: is the value function at state is the set of possible actions is the reward for taking action in state is the discount factor is the probability of transitioning to state from state when taking action Key Components of Dynamic Programming Optimal Substructure A problem exhibits optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems. Mathematically, if we denote the optimal solution to problem as , and if can be divided into subproblems , then: where is some combining function. Overlapping Subproblems Dynamic programming is most effective when subproblems recur multiple times. By storing solutions to subproblems (memoization), we avoid redundant calculations. If is the time complexity of a naive recursive algorithm and is the number of distinct subproblems, then dynamic programming reduces the time complexity to , where is the time to solve each subproblem after its subproblems are solved. Types of Dynamic Programming Top-Down Approach (Memoization) The top-down approach starts with the original problem and recursively breaks it down into subproblems, storing solutions in a table (often called a memo) to avoid redundant calculations: 1. Check if the solution to the current subproblem is already in the memo 2. If yes, return the stored result 3. If no, solve the subproblem recursively and store the result in the memo Pseudocode: function solve(problem): if problem in memo: return memo[problem] if problem is base case: return base case solution result = recursive calculation using solve() on subproblems memo[problem] = result return result Bottom-Up Approach (Tabulation) The bottom-up approach starts by solving the smallest subproblems first and builds up to the original problem: 1. Identify the order in which subproblems should be solved 2. Solve all subproblems in this order 3. Use the solutions of smaller subproblems to solve larger ones Pseudocode: function solve(problem): initialize table for all subproblems fill base cases in the table for each subproblem in order of increasing size: solve using solutions to smaller subproblems return table[original problem] Classic Dynamic Programming Problems Shortest Path Problems The Floyd-Warshall algorithm finds shortest paths between all pairs of vertices in a weighted graph. The recurrence relation is: where is the shortest path from vertex to vertex using only vertices as intermediate vertices. Knapsack Problem Given items with weights and values , and a knapsack with capacity , the goal is to maximize the total value while keeping the total weight under . Let be the maximum value achievable using items through with weight limit . The recurrence relation is: if if Longest Common Subsequence Given two sequences and , find the longest subsequence present in both sequences. Let be the length of the longest common subsequence of and . The recurrence relation is: Matrix Chain Multiplication Given a sequence of matrices , find the most efficient way to multiply these matrices together. Let be the minimum number of scalar multiplications needed to compute the matrix product . The recurrence relation is: where is the dimension such that matrix has dimensions . Applications in Various Fields Economics and Finance Dynamic programming is used in portfolio optimization, option pricing (Black-Scholes model), and resource allocation problems. For instance, in stochastic control problems, the Hamilton-Jacobi-Bellman equation: forms the basis for many financial optimization models. Bioinformatics Sequence alignment algorithms like Needleman-Wunsch and Smith-Waterman use dynamic programming to find optimal alignments between DNA, RNA, or protein sequences. Computer Science Dynamic programming is essential in algorithm design for problems like string matching, parsing, and graph algorithms. The Viterbi algorithm for hidden Markov models uses the recurrence: where is the probability of the most likely state sequence ending in state at time . Limitations and Considerations While powerful, dynamic programming has limitations: The problem must exhibit both optimal substructure and overlapping subproblems Space complexity can be significant for problems with many states Formulating the recurrence relation correctly is often challenging Some problems require additional techniques like state space reduction Exercises 1. Prove that the Fibonacci sequence calculation exhibits both optimal substructure and overlapping subproblems. 2. Develop a dynamic programming solution for the coin change problem: given coins of denominations and an amount , find the minimum number of coins needed to make change for . 3. Analyze the time and space complexity of the bottom-up and top-down approaches for solving the knapsack problem. 4. Implement the Floyd-Warshall algorithm and test it on a weighted graph with negative edges (but no negative cycles). 5. Research and explain how dynamic programming is applied in reinforcement learning algorithms.