Knowt
L-5.1: Introduction to Dynamic Programming | Greedy Vs Dynamic Programming | Algorithm(DAA)
Chapter 1: Introduction
Dynamic programming is used to solve optimization problems.
Optimization problems involve finding the optimal answer, either maximum or minimum.
Dynamic programming differs from the greedy method in its approach to solving optimization problems.
Chapter 2: Say The Cost
The greedy method chooses the minimum cost path at each stage.
It may not always give the correct answer, as it does not consider future costs.
Dynamic programming considers all paths and makes decisions based on the optimal solution.
Chapter 3: Overlapping Subproblems
Greedy and dynamic programming divide the problem into overlapping subproblems.
Dynamic programming always gives the optimal answer, while greedy may or may not.
Dynamic programming combines the solutions of subproblems to reach a final solution.
Chapter 4: Example Of Fibonacci
Dynamic programming involves solving repeated subproblems.
The solutions to these subproblems are stored to avoid solving them again.
The Fibonacci series is an example of a problem that can be solved using dynamic programming.
Chapter 5: Store These Subproblems
Optimal substructure means dividing a problem
Able to divide the problem
Overlapping subproblem means repeating subproblems
Store the data in a table to avoid solving them again
Dynamic programming stores subproblems and their results
Prevents exponential time complexity
Dynamic programming is the foundation of solving various problems
Matrix Chain Multiplication
Multi-Stage Graph
Traveling Salesman Problem
Longest Common Subsequence
Sum of Subset Problem
All Pair Shortest Path
0-1 Knapsack
Chapter 6: Conclusion
L-5.1: Introduction to Dynamic Programming | Greedy Vs Dynamic Programming | Algorithm(DAA)
Chapter 1: Introduction
Dynamic programming is used to solve optimization problems.
Optimization problems involve finding the optimal answer, either maximum or minimum.
Dynamic programming differs from the greedy method in its approach to solving optimization problems.
Chapter 2: Say The Cost
The greedy method chooses the minimum cost path at each stage.
It may not always give the correct answer, as it does not consider future costs.
Dynamic programming considers all paths and makes decisions based on the optimal solution.
Chapter 3: Overlapping Subproblems
Greedy and dynamic programming divide the problem into overlapping subproblems.
Dynamic programming always gives the optimal answer, while greedy may or may not.
Dynamic programming combines the solutions of subproblems to reach a final solution.
Chapter 4: Example Of Fibonacci
Dynamic programming involves solving repeated subproblems.
The solutions to these subproblems are stored to avoid solving them again.
The Fibonacci series is an example of a problem that can be solved using dynamic programming.
Chapter 5: Store These Subproblems
Optimal substructure means dividing a problem
Able to divide the problem
Overlapping subproblem means repeating subproblems
Store the data in a table to avoid solving them again
Dynamic programming stores subproblems and their results
Prevents exponential time complexity
Dynamic programming is the foundation of solving various problems
Matrix Chain Multiplication
Multi-Stage Graph
Traveling Salesman Problem
Longest Common Subsequence
Sum of Subset Problem
All Pair Shortest Path
0-1 Knapsack
Chapter 6: Conclusion
