[10] Programación Dinámica

Understanding Dynamic Programming

Introduction to Problem Solving

• Dynamic programming allows for solving complex problems by breaking them down into smaller subproblems, integrating their solutions.

Example: Fibonacci Sequence

• The Fibonacci sequence is introduced as an example where each number is the sum of the two preceding ones, starting with 1 and 2.

• For n < 2 , the function returns n ; for n geq 2 , it recursively calls itself for n - 1 and n - 2 .

Computational Complexity

• Using a recursive approach results in exponential time complexity of O(2^n) due to repeated calculations. For instance, calculating Fibonacci(5) involves multiple redundant computations.

• The inefficiency becomes apparent when visualizing the calculation tree, highlighting how many times certain values are recalculated unnecessarily.

Optimization through Memoization

• To improve efficiency, dynamic programming stores previously computed results (memoization), allowing reuse in future calculations without recomputation. This can be done using tables or arrays.

• It’s emphasized that dynamic programming is suitable for problems that can be divided into overlapping subproblems where previous results can aid in solving larger issues.

Formal Definition and Conditions

• Dynamic programming is defined as an optimization technique used for overlapping problems, utilizing memoization to solve complex issues efficiently. Two key conditions must be met:

• Optimal Substructure: Solutions to larger problems depend on optimal solutions to smaller subproblems. This adheres to the principle of optimality.

• Overlapping Subproblems: Some subproblems recur multiple times within the problem space, making memoization beneficial.

Identifying Suitable Problems

• Not all problems are suited for dynamic programming; typically those involving recursion may benefit from this approach.

• Examples include classic problems like the knapsack problem and shortest path algorithms (e.g., Dijkstra's algorithm). These are often documented extensively in literature on algorithms.

• Other applicable scenarios involve task scheduling and resource allocation in fields such as engineering and finance, aiming at optimizing processes while reducing computational complexity.

Dynamic Programming Techniques

Overview of Dynamic Programming

• Dynamic programming is an efficient method for solving complex problems by breaking them down into simpler subproblems, allowing for optimal solutions without unnecessary recalculations.

• It can be applied to a wide range of fields including artificial intelligence, finance, and biological sciences, showcasing its versatility in problem-solving.

Advantages and Disadvantages

• The primary advantage of dynamic programming is its ability to reduce computational complexity; however, it requires significant storage space due to data retention for future use.

• Implementing dynamic programming can be challenging and may not always yield the most efficient solution compared to other techniques.

Approaches to Dynamic Programming

Top Down Approach

• The top-down approach involves solving the problem recursively from the top of a conceptual tree downwards, calculating only what is necessary as needed.

• This method utilizes recursion while storing previously computed results in memory to avoid redundant calculations.

Bottom Up Approach

• In contrast, the bottom-up approach builds solutions from the ground up by precomputing all necessary values before arriving at the final result.

Implementation Steps

Top Down Implementation Details

• The top-down technique maintains a recursive structure but adds memory storage for previously calculated results using a dictionary-like structure (caching).

• Caching allows frequently used data to be accessed quickly during computations, enhancing efficiency.

Key Steps in Coding Dynamic Programming Solutions

1. Space Allocation: Create a variable or structure to store computed values.

2. Define Subproblem Keys: Establish keys that represent each subproblem's state.

3. Base Case Addition: Include base cases that check if a solution has already been computed.

4. Recursive Calculation: Calculate Fibonacci numbers recursively while storing results in memory before returning them.

Example Walkthrough

• An example implementation begins with checking if n is less than 2; if so, return n. Otherwise, compute Fibonacci recursively as Fibonacci(n - 1) + Fibonacci(n - 2) while incorporating caching strategies.

Dynamic Programming: Top-Down Approach to Fibonacci

Understanding the Top-Down Dynamic Programming Technique

• The discussion begins with an introduction to applying the top-down dynamic programming technique to calculate Fibonacci numbers, specifically for N = 5.

• The recursive function is invoked with N = 5, and a map (or cache) is initialized to store computed values. The key for this computation will be 5.

• Since the map is initially empty, it checks if the key (5) exists in the map; it does not, so it proceeds to compute Fibonacci(4).

Recursive Calls and Pending Calculations

• As Fibonacci(4) is called, it again checks the map for key 4. Not found, so it stores key 4 and prepares to compute Fibonacci(3), leaving this calculation pending.

• The process continues recursively downwards: calling Fibonacci(3), which then calls Fibonacci(2), each time checking if the value has already been computed and stored in the map.

Base Cases and Storing Results

• When reaching base cases like Fibonacci(1), it finds that it's less than 2. It stores this result directly into the map as both keys (1 and 0).

• Upon returning from these base cases, previously pending calculations can now utilize stored results from the map instead of recalculating them.

Completing Calculations Using Cached Values

• As recursion unwinds back up through previous calls (Fibonacci(2), then Fibonacci(3)), cached values are used effectively. For instance, when calculating Fibonacci(3), it retrieves its value from the map rather than recalculating.

• Ultimately, by leveraging previously computed values stored in the cache/map throughout recursive calls, it efficiently computes Fibonacci(5). This demonstrates how dynamic programming optimizes performance by avoiding redundant calculations.

Transitioning to Bottom-Up Approach

• After explaining the top-down approach's efficiency through caching results, a transition is made towards discussing a bottom-up approach that resolves smaller known problems first before building larger solutions based on those results.

• This method requires a single-dimensional table corresponding to parameter N for storing intermediate results as they are calculated sequentially.

Understanding Fibonacci Sequence Calculation

Steps to Build the Fibonacci Table

• The process begins with using a graph to construct a table, understanding each element's meaning, and incrementally filling it based on resolution strategy.

• The discussion focuses on the Fibonacci sequence, starting from the established graph structure.

Graph Representation of Fibonacci Elements

• The graph captures all elements leading up to Fibonacci(5), including Fibonacci(4), (3), (2), (1), and (0).

• This representation allows for generating a one-dimensional table or vector to store values F5, F4, F3, F2, F1, and F0.

Filling the Fibonacci Table Incrementally

• Solutions are built from smaller problems towards larger ones; thus, the vector is reversed to start from zero and work up to F5.

• Initial values in the table are defined as 0 and 1. Subsequent values are calculated as sums of previous two entries.

Calculating Values in the Table

• For example, calculating Fibonacci(2) involves summing its two predecessors: 1 + 1 = 2. This pattern continues for higher indices.

• The code implementation starts by creating a table that accommodates one more than needed elements. A loop fills this table based on prior calculations.

Returning Results from the Table

• The return value is specified as the entry at position N in the table. This approach ensures clarity about what result is being sought.

Optimizing Memory Usage in Fibonacci Calculation

Reducing Memory Footprint

• To find larger Fibonacci numbers without expanding memory usage significantly, only necessary variables are retained instead of an entire table.

Efficient Variable Management

• By maintaining just three variables—previous two results—the algorithm can compute results efficiently without storing all intermediate values.

Comparing Top Down vs Bottom Up Approaches

Memory Considerations

• Top-down approaches may use more memory due to dense tables while bottom-up methods optimize space by calculating only what's necessary.

Risk of Overflow

• Bottom-up algorithms risk overflow if not managed properly since they calculate everything upfront rather than selectively.

Conclusion on Methodologies

Power of Bottom-Up Approach

• Generally considered more powerful due to potential space optimization; however, effectiveness can depend on problem specifics and parameterization needs.

Dynamic Programming Strategies and Problem Solving

Memory Management in Dynamic Programming

• The choice between top-down and bottom-up approaches in dynamic programming can significantly affect memory usage. Top-down may use less memory as it only stores necessary values, while bottom-up requires a complete table.

• In the top-down approach, the number of keys stored is uncertain, which can lead to stack overflow due to dynamic memory allocation.

• Bottom-up tabulation is considered safer as it uses a predefined static table, reducing the risk of running out of memory.

Visualizing Problems with Graphs

• A directed acyclic graph (DAG) can help identify subproblems and their relationships, allowing for effective problem-solving through dynamic programming.

• Understanding these relationships enables generalization and implementation of solutions by solving subproblems in the correct order.

Case Study: The House Robber Problem

• The problem involves maximizing money stolen from houses arranged linearly, where robbing two adjacent houses is prohibited. Example values are provided for clarity.

• Participants are encouraged to brainstorm potential solutions within a set time frame before discussing their ideas collectively.

Initial Solution Approaches

• One participant suggests selecting the highest value among pairs but realizes that this method could overlook optimal combinations due to adjacency restrictions.

• Another participant proposes summing values while skipping one house at a time but acknowledges limitations in this strategy regarding possible combinations.

Exploring Combinatorial Solutions

• Discussion reveals that multiple combinations exist beyond simple pair selections; participants explore various strategies for maximizing total theft without violating adjacency rules.

• The complexity increases as participants consider different scenarios where non-adjacent houses might yield better results than initially thought.

Refining Strategies

• A new idea emerges about always starting with the highest value house and checking adjacent sums to determine if they provide a better outcome than simply taking the highest single value.

• This iterative approach highlights potential pitfalls in greedy algorithms, emphasizing that local maxima do not guarantee global optimization across all possible combinations.

Dynamic Programming in Problem Solving

Understanding Combinations and Choices

• The discussion begins with the idea of selecting combinations of numbers based on their arrangement, emphasizing that sometimes a lower number can yield better results than simply choosing the highest.

• The speaker illustrates how different combinations can affect outcomes, suggesting that strategic selection is more important than merely picking the largest available option.

• Acknowledgment of the complexity in decision-making; it's not just about choosing the highest number but finding the best path among options.

Evaluating Paths and Outcomes

• The conversation shifts to evaluating paths taken when making choices, highlighting that skipping certain options may lead to better overall results.

• Emphasizes comparing potential outcomes from different paths (e.g., choosing between 6 or 8), indicating a need for thorough analysis before making decisions.

Introduction to Dynamic Programming Techniques

• The instructor notes that previous suggestions did not incorporate dynamic programming techniques, which involve storing values to solve subproblems efficiently.

• An example is provided where a table is used to track gains from robbing houses, illustrating how dynamic programming can optimize decision-making processes.

Recursive Function Development

• The concept of defining a recursive function (robar) is introduced, aimed at calculating maximum gains while considering previous decisions.

• Discussion on comparing potential gains from various choices (e.g., whether to rob house three), reinforcing the importance of evaluating all possibilities.

Building Towards Optimal Solutions

• Explanation of how results are stored in a table for future reference, preventing redundant calculations and enhancing efficiency in problem-solving.

• Further elaboration on maximizing gains by comparing current choices against previously calculated values, demonstrating practical application of dynamic programming principles.

Finalizing Results and Learning Points

• As calculations progress through examples, participants learn how to derive optimal solutions by systematically analyzing each choice's impact on total gain.

• Concludes with an emphasis on understanding what needs to be stored for effective use of dynamic programming techniques in problem-solving scenarios.

New Exercise Proposal: Gold Mining Problem

• A new exercise involving navigating through a grid representing gold mines is introduced. Participants must strategize movement downwards or diagonally to maximize gold collection while adhering to movement constraints.

Dynamic Programming Approach to Problem Solving

Introduction to the Problem

• The exercise begins with a reference to obtaining a value starting from 15, moving through various numbers (17, 32, and 9).

• The speaker encourages participants to think about how to solve the problem collaboratively, suggesting that they can discuss their ideas as they arise.

Exploring Options

• Starting at position 15 opens up three potential paths downwards: towards 7, 11, or 17. This sets the stage for evaluating maximum values.

• The discussion highlights the need to calculate maximum values among these options while acknowledging that brute force may not be efficient due to multiple pathways.

Transitioning from Brute Force to Dynamic Programming

• A shift is made from brute force methods toward dynamic programming as a more effective solution strategy.

• The concept of using recursion with parameters related to a matrix is introduced as part of this dynamic programming approach.

Accumulating Values

• Participants are encouraged to visualize accumulated values in a grid format as they progress through the problem.

• An example calculation is provided where participants consider accumulating values based on previous steps (e.g., comparing results from different paths).

Final Calculations and Results

• As calculations continue, participants determine which path yields the highest accumulated value (31 in this case).

• The final step involves identifying the maximum value in the last row of their calculations, leading them back to an overall result of 73.

Conclusion and Reflection on Dynamic Programming

• The session concludes with reflections on dynamic programming's effectiveness in solving complex problems compared to traditional methods.

Dynamic Programming Challenges and Sudoku

Introduction to Dynamic Programming

• The discussion begins with a comparison of current programming challenges to previous ones, highlighting the complexity of dynamic programming problems.

• A specific problem is introduced: calculating the edit distance between two words, defined as the minimum number of insertions, deletions, or substitutions needed to transform one word into another.

Edit Distance Example

• An example illustrates how to compute the edit distance by detailing steps such as deleting characters and adding new ones to transition from one word to another.

Sudoku and Dynamic Programming

• The conversation shifts to whether Sudoku can be solved using dynamic programming techniques. Participants are encouraged to think critically about this question.

• Key constraints of Sudoku are discussed, including the requirement that numbers 1 through 9 must not repeat in rows or columns within a 3x3 grid.

Constraints and Problem Solving

• Further elaboration on Sudoku's structure emphasizes its matrix-like nature and restrictions on number placement.

• Participants express uncertainty about solving Sudoku with dynamic programming due to varying input conditions affecting solvability.

Conclusion on Sudoku's Solvability

• It is concluded that while some aspects may lend themselves to dynamic programming, overall, Sudoku does not fit neatly into this approach due to its unique constraints.

Recreational Break and Pedregal Problem

Transitioning Activities

• The session transitions into a break where students are invited to engage in an activity related to a previously discussed problem known as "Construyendo una casa en el pedregal."

Task Assignment

• Students are tasked with reading about the Pedregal problem during their break and considering potential solutions using dynamic programming principles.

Reflection on Previous Discussions

• There’s an emphasis on recalling past discussions regarding the Pedregal problem, indicating its relevance for upcoming lessons.