Dynamic programming bursting balloons
Let’s use an example of a dynamic programming problem to illustrate the concept. I didn’t choose an easy example, since it would fit more in the 2D Dynamic Programming category.
This problem cannot be solved using a greedy approach, as the optimal solution requires considering all possible orders of bursting balloons.
State: A state represents a unique configuration of the problem that encapsulates all the necessary information, to make decisions and compute results for that specific sub-problem.
Base Case: The base case is the simplest, smallest instance of the problem that can be solved directly without further recursion or iteration, serving as the foundation for building up the solution.
Transition: The transition defines the relationship between the current state and smaller sub-problems, specifying how to compute the result for a larger problem using the results of its sub-problems.
We can implement this solution either iteratively (building the state bottom-up from the base case to get the next until the optimal one), or recursively (solving problem by applying getting the optimal solution through recursively building top-down the state).
