Minimum Steps to One Problem - Solution Using Top-Down DP

Solution: Top-Down Dynamic Programming approach

The recursion tree for the previous solution results in subproblem overlapping. We can improve the solution using dynamic programming.

There can be two types of approaches in dynamic programming.

In Top-Down, you start building the big solution right away by explaining how you build it from smaller solutions. Generally, you will use recursion in this approach. You will get the answer when you hit the base condition. This method is also called memoization. Let’s understand with an example :

• I will be an amazing coder. How?
• I will work hard like crazy. How?
• I’ll practice more and try to improve. How?
• I’ll start taking part in contests. How?
• I’ll be practicing. How?
• I’m going to learn to program.

So let’s start with the Top-Down approach.