Gain insights into dynamic programming, explore recursion basics, and delve into advanced techniques like Bottom-Up optimization. Discover ways to solve complex problems more efficiently with hands-on coding challenges.

Dynamic programming is something every developer should have in their toolkit. It allows you to optimize your algorithm with respect to time and space — a very important concept in real-world applications.

In this course, you’ll start by learning the basics of recursion and work your way to more advanced DP concepts like Bottom-Up optimization. Throughout this course, you will learn various types of DP techniques for solving even the most complex problems. Each section is complete with coding challenges of varying difficulty so you can practice a wide range of problems.

By the time you’ve completed this course, you will be able to utilize dynamic programming in your own projects.

Dynamic Programming in Python: Optimizing Programs for Efficiency

# Tabulation

As we discussed in the **bottom-up** approach, we start from the bottom, the smallest subproblem, or the base case. After evaluating the base case, we evaluate a slightly bigger problem and store its result. We continue doing this, i.e., build on the solution of smaller subproblems to evaluate bigger and bigger subproblems until we find the solution to our main problem.


In bottom-up dynamic programming, the process of storing results of evaluated subproblems in an array is called **tabulation**.

# How is it different from memoization?

In memoization and top-down dynamic programming, we evaluated and stored results on an ad-hoc basis. We only evaluated something when it was needed. This means if a problem depends on only two subproblems, only those subproblems would have been evaluated. This comes naturally from the design of recursion. Moreover, the order in which we evaluated subproblems did not matter either. Evaluating *Fibonacci(n)* before *Fibonacci(n-1)* or vice versa did not have any effect on the result or running time of the algorithm.

This is not the case with tabulation. Here, we will have to evaluate almost every subproblem that lies between the base case and the main problem and we will have to do so in order. Thus, in tabulation, we typically use lists and arrays instead of hashtables. Lists force us to start from scratch and solve everything sequentially, which is the crux of bottom-up dynamic programming as well. For example, if we were writing an algorithm for the factorial of a number `n` using a bottom-up approach, we first establish a factorial of `0`, then we will use it for factorial of `1`, `2` and so on until we reach `n`. We can tabulate the results by keeping a list of size `n`, where each index will store the factorial against that index. For example at index `4`, we will store `4!`. Look at the code of the factorial algorithm below.

We have also given the code for a recursive algorithm to evaluate the factorial for comparison.

In this lesson, we will learn about a technique to store results of evaluated subproblems in bottom-up dynamic programming.


Chapter 1: From Recursion to Dynamic Programming

Chapter 2: Top-Down Dynamic Programming with Memoization

Chapter 3: Bottom-Up Dynamic Programming with Tabulation

Chapter 4: Practice Problems

What is Tabulation?

Tabulation