📊Mathematical Methods for Optimization Unit 18 – Dynamic Programming

What's Dynamic Programming?

• Optimization technique breaks complex problems into simpler subproblems
• Solves each subproblem once stores the solution in a memory-based data structure (memoization)
• Combines solutions to subproblems to solve the original complex problem
• Follows the Principle of Optimality any optimal solution to a problem is composed of optimal solutions to its subproblems
• Applicable to problems exhibiting overlapping subproblems optimal substructure
  • Overlapping subproblems subproblems are reused several times (Fibonacci sequence)
  • Optimal substructure optimal solution can be constructed from optimal solutions of its subproblems (shortest path problem)
• Differs from greedy algorithms considers multiple choices at each step
• Improves efficiency by avoiding redundant calculations of subproblems

Key Concepts and Terminology

• Memoization technique of storing previously computed results to avoid redundant calculations
• Recursive formulation expresses the solution in terms of smaller subproblems
• Optimal substructure property optimal solution can be constructed from optimal solutions of its subproblems
• Overlapping subproblems property subproblems are reused multiple times in the overall solution
• State variables set of parameters that uniquely define a subproblem
• Stage each step in the problem-solving process where a decision is made
• Principle of Optimality states that an optimal solution has the property that whatever the initial state and initial decisions are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decisions
• Bellman equation recursive equation that relates the value of a problem to the value of its subproblems

Stages of Dynamic Programming

• Problem formulation identify the objective function and constraints
• Identifying subproblems break down the problem into smaller subproblems
• Defining the recursive relation express the solution in terms of solutions to smaller subproblems
• Constructing the memoization table build a table to store the solutions of subproblems
• Filling the memoization table compute solutions to subproblems in a bottom-up manner
• Extracting the optimal solution trace back the memoization table to construct the optimal solution
• Optimizing the solution improve the time and space complexity of the solution if possible

Common Problem Types

• Optimization problems aim to maximize or minimize a certain objective function (knapsack problem, resource allocation)
• Counting problems count the number of ways to achieve a certain objective (coin change problem, number of paths)
• Sequence problems find a sequence that satisfies certain conditions (longest increasing subsequence, shortest path)
• Subset problems find a subset of elements that satisfy certain constraints (subset sum problem)
• Partition problems divide a set into subsets that satisfy certain properties (matrix chain multiplication)
  • Matrix chain multiplication find the optimal way to parenthesize a sequence of matrix multiplications to minimize the number of scalar multiplications
• Optimal ordering problems determine the optimal order in which to perform a set of tasks (assembly line scheduling)
• Optimal search problems search for a solution in a solution space that satisfies certain criteria (traveling salesman problem)

Solving Techniques and Strategies

• Top-down approach starts with the original problem and recursively breaks it down into subproblems
  • Solves subproblems as needed memoizes their solutions to avoid redundant calculations
  • Often implemented using recursive functions
• Bottom-up approach starts with the smallest subproblems and progressively combines their solutions to solve larger subproblems
  • Typically uses iteration to fill the memoization table
  • Avoids recursive overhead can be more efficient than top-down approach
• Memoization stores the results of expensive function calls returns the cached result when the same inputs occur again
• Tabulation builds a table in a bottom-up fashion and returns the last entry from the table
• Optimal substructure identify if the problem can be solved by combining optimal solutions to subproblems
• Overlapping subproblems determine if the problem has subproblems that are reused multiple times
• Reconstruct the solution trace back the memoization table to build the optimal solution

Real-World Applications

• Optimization in transportation networks (shortest path problem, traveling salesman problem)
• Resource allocation in finance and economics (knapsack problem, investment strategies)
• Bioinformatics sequence alignment, phylogenetic tree construction
• Computer vision image segmentation, object detection
• Natural language processing text summarization, machine translation
• Robotics motion planning, control optimization
• Networking routing protocols, network flow optimization
• Compiler design instruction scheduling, register allocation

Pros and Cons

• Pros:
  • Solves complex problems by breaking them down into simpler subproblems
  • Avoids redundant calculations by memoizing subproblem solutions
  • Provides a general framework for solving optimization problems
  • Offers optimal solutions to problems with optimal substructure
  • Reduces time complexity compared to brute-force approaches
• Cons:
  • Requires careful problem formulation and identification of subproblems
  • May have high space complexity due to memoization
  • Not suitable for all problems some may not have optimal substructure or overlapping subproblems
  • Can be overkill for simple problems with efficient greedy solutions
  • May be challenging to implement and debug compared to simpler approaches

Practice Problems and Examples

• Fibonacci sequence find the nth Fibonacci number
  • Recursive solution has exponential time complexity
  • Dynamic programming solution reduces time complexity to linear
• Knapsack problem maximize the total value of items in a knapsack with a weight limit
  • Subproblems consider subsets of items and different weight limits
  • Memoization table stores the maximum value for each subproblem
• Longest common subsequence find the longest subsequence common to two sequences
  • Subproblems consider prefixes of the sequences
  • Memoization table stores the length of the LCS for each subproblem
• Coin change problem find the number of ways to make change for a given amount using a set of coins
  • Subproblems consider smaller amounts and subsets of coins
  • Memoization table stores the number of ways for each subproblem
• Edit distance find the minimum number of operations (insert, delete, replace) to transform one string into another
  • Subproblems consider prefixes of the strings
  • Memoization table stores the minimum edit distance for each subproblem