Dynamic Programming (DP) Tutorial with Problems

Dynamic Programming

Table of Contents

• 1. Introduction to Dynamic Programming
• 2. Applications
• 3. Steps to solve a DP Problem
• 4. Approaches to Dynamic Programming
• 5. Example: Fibonacci Sequence
• 6. Example: Knapsack Problem
• 7. Leetcode Problems
• 8. References

1 Introduction to Dynamic Programming

Dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems and optimal substructure, which are described below:

• Overlapping subproblems

  A problem has overlapping subproblems if it can be broken down into subproblems which are reused several times. For example, in the Fibonacci sequence, to calculate Fib(5), one needs Fib(4) and Fib(3), but Fib(4) itself requires Fib(3) and Fib(2). Here, Fib(3) is calculated multiple times, which is an overlapping subproblem.

• Optimal substructure

  A problem has an optimal substructure if an optimal solution to the problem contains within it optimal solutions to the subproblems. For instance, in the shortest path problem, if the shortest path from point A to point C goes through point B, then the shortest path from A to B is also part of the shortest path from A to C.