Dynamic Programming Characteristics

Dynamic programming is a way of solving tricky problems by breaking them into smaller pieces and solving each piece just once, saving the answers to avoid doing the same work over and over.

Here are two key things to check if dynamic programming is the right tool for the job:

1. Optimal Substructure:

• The problem should have optimal substructure, meaning the best solution comes from combining optimal solutions to smaller sub-problems.
• Take the Fibonacci series as an example, where the nth number is the sum of the previous two numbers: Fib(n) = Fib(n-1) + Fib(n-2).
• This shows how a problem of size “n” can be broken down into sub-problems of size “n-1” and “n-2,” helping define the base cases of the recursive algorithm (e.g., f(0) = 0, f(1) = 1).

2. Overlapping Subproblems:

• The other essential characteristic is overlapping subproblems, where the same smaller problems occur repeatedly in a recursive manner.
• By recognizing and storing the solutions to these overlapping subproblems, algorithm performance can be significantly improved.
• In the Fibonacci dynamic programming example, the tree representation reveals that sub-problems like fib(4), fib(3), fib(2), etc., appear multiple times.
• Remember, for a problem to be a good fit for dynamic programming, it needs both optimal substructure and overlapping subproblems.

Dynamic programming, popularly known as DP, is a method of solving problems by breaking them down into simple, overlapping subproblems and then solving each of the subproblems only once, storing the solutions to the subproblems that are solved to avoid redundant computations. This technique is useful for optimization-based problems, where the goal is to find the most optimal solution among all possible set of solutions.