Dynamic programming patterns notes

Dynamic Programming (DP) → Definition

A method for solving complex problems by breaking them down into simpler subproblems, solving each just once, and storing their solutions.

True or False: DP requires overlapping subproblems.

True. DP is effective when a problem can be broken down into overlapping subproblems that can be solved independently.

Fill in the blank: DP is used to optimize __________.

decisions and resource allocations in problems with optimal substructure.

Optimal Substructure → Explanation

A property where an optimal solution to a problem contains optimal solutions to its subproblems.

Comparison: Recursion vs. Dynamic Programming

Recursion: solves subproblems independently. DP: solves subproblems once and stores results.

Memoization → Definition

An optimization technique where intermediate results are stored to avoid redundant calculations in recursive algorithms.

Tabulation → Definition

An iterative approach to DP where results are built up in a table (array) from bottom to top.

True or False: DP can only be used in polynomial time.

False. Some DP problems can be solved in exponential time, but many can be optimized to polynomial time.

Example: Fibonacci Sequence using DP

Using DP, Fibonacci(5) can be calculated as: Fibonacci(5) = Fibonacci(4) + Fibonacci(3) with stored results.

State and Transition → Explanation

State: Represents a solution at a certain point. Transition: The way to move from one state to another.

Bottom-Up vs. Top-Down Approach

Bottom-Up: Builds solutions from smallest to largest. Top-Down: Solves larger problems first using recursion.

Cause → Effect: Using DP reduces computation time.

By storing results of subproblems, DP avoids recalculating solutions, significantly speeding up overall solving time.

Overlapping Subproblems → What does it mean?

When a problem can be broken down into smaller, repeating subproblems that can be solved independently.

True or False: Dynamic programming solves problems without overlapping subproblems.

False. Dynamic programming is specifically used for problems with overlapping subproblems.

Optimal Substructure → Definition?

A problem exhibits optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems.

Memoization → What is it?

A top-down technique that stores results of expensive function calls and returns the cached result when the same inputs occur again.

Bottom-Up Approach → Explain briefly.

A method that solves all possible small subproblems first and uses their solutions to build up solutions to larger problems.

Fill in the blank: In dynamic programming, we use _____ to store results.

arrays or tables

Fibonacci Sequence problem → How is it solved?

Using dynamic programming, we store previous Fibonacci numbers in an array: $\displaystyle F(n) = F(n-1) + F(n-2)$.

Comparison: Memoization vs. Tabulation.

Memoization is top-down with recursion, while tabulation is bottom-up with iterative filling of a table.

Knapsack Problem → Definition?

A problem where you must maximize the total value of items packed in a knapsack without exceeding its weight limit.

Sequence Alignment → What does it achieve?

It finds the optimal way to align two sequences (like DNA) to maximize matches and minimize gaps.

Longest Common Subsequence → Explanation?

The longest sequence that appears in the same order in both sequences but not necessarily consecutively.

Coin Change Problem → What is it?

Given coins of different denominations, find the minimum number of coins that make a certain amount.

True or False: Dynamic programming requires a greedy approach.

False. Dynamic programming does not rely on greedy strategies but rather on optimal substructure.

Edit Distance → Purpose?

To calculate the minimum number of operations (insertions, deletions, substitutions) required to transform one string into another.

Matrix Chain Multiplication → What does it determine?

The most efficient way to multiply a given sequence of matrices by minimizing the number of scalar multiplications.

Traveling Salesman Problem → Briefly explain.

A problem of finding the shortest possible route that visits each city exactly once and returns to the origin city.

Optimal Binary Search Tree →

A dynamic programming approach to minimize search time in a frequency-sorted tree structure by calculating the optimal arrangement of keys.

True or False: Fibonacci sequence can be solved using dynamic programming.

True. Using dynamic programming, we can store previously calculated Fibonacci numbers to avoid redundant calculations.

Fill in the blank: The __________ problem involves finding the shortest path in weighted graphs.

Bellman-Ford algorithm.

Knapsack problem →

A classic optimization problem where you maximize value within a weight constraint by selecting items. Dynamic programming efficiently explores combinations.

Question: How is dynamic programming applied in stock trading?

It optimizes buy/sell decisions over time considering past states to maximize profit.

Cost of Edit Distance →

Dynamic programming calculates the minimum operations (insertions, deletions, substitutions) required to convert one string into another.

Comparing LCS and subsequence problems:

Longest common subsequence finds the longest sequence present in both strings, while subsequence checks for order without requirement of contiguity.

True or False: Dynamic programming can be used in game development.

True. It helps optimize strategies in decision-making processes, like minimizing losses or maximizing scores.

Question: How does dynamic programming help in resource allocation?

It allows for optimal distribution of limited resources across competing tasks by evaluating the best combinations.

Matrix Chain Multiplication →

Dynamic programming determines the most efficient way to multiply a given sequence of matrices by minimizing the number of operations.

Dynamic programming in finance: Example →

Portfolio optimization uses dynamic programming to balance returns and risks, considering multiple investment scenarios.

Question: Why is the Traveling Salesman Problem relevant?

It illustrates the challenges of finding the shortest route visiting multiple locations, solvable using dynamic programming for efficiency.