Minimum Steps to One Problem - Solution Using Bottom-Up DP

Implement another optimized solution for the problem discussed in the previous lesson.

Solution: Bottom-Up Dynamic Programming approach

In Bottom-Up, you start with the small solutions and use these to build up larger solutions. You will use an array to get the smaller solutions and build them to get the final solution. This method is also called tabulation. Let us understand with an example :

  • I’m going to learn to program.
  • Then, I will start practicing.
  • Then, I will start taking part in contests.
  • Then, I’ll practice even more and try to improve.
  • After working hard like crazy,
  • I’ll be an amazing coder.

For almost all the problems, we will create both types of solutions. As an exercise for you, one of the solutions to some problems will be skipped.

Let’s look at the Bottom-Up approach now.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.