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