Unraveling Dynamic Programming

Deconstructing a core approach to competitive programming

What is dynamic programming?

When participating in competitive programming there are many ways to approach a problem. However, some approaches are more optimal than others, and among these optimal approaches is dynamic programming.

Dynamic programming (DP), in the context of problem-solving, is an algorithmic technique for solving optimization problems by breaking them down into simpler subproblems. A key aspect of DP is the fact that the optimal solution to a problem depends on the solution to its individual subproblems.

Identifying when to use dynamic programming

In theory, any problem can be solved through dynamic programming. However, this does not mean that dynamic programming is a suitable approach to all problems. We can identify when a problem is best solved via dynamic programming as follows:

• Is the problem an optimization problem?

  • Keep an eye out for terms such as “longest/shortest,“ “minimized/maximized,“ “least/most,“ etc.

• Can recursion be used to arrive at a solution?

  • If it can, then the problem is a good candidate for DP.

• Does the problem contain optimal substructure?

  • Optimal substructure is a specific property of problems where the optimal solution to the problem can be constructed from optimal solutions of its subproblems.

  • DP is particularly effective on problems that have optimal substructure.

Dynamic programming approaches

There are two main approaches to DP:

Memoization (top-down approach)

Memoization is an optimization process for improving the performance of recursive algorithms. Problems are solved by recursively finding the solution to their subproblems. These solutions are cached (as a means to prevent function call overhead) and are eventually returned when needed. This is why the process is called memoization—a memo, or a “note to self,“ is created for the values returned from solving each problem. Memoization is preferred if only some of the subproblems need to be solved for the original problem to be solved (this is due to the lazy solving of the subproblems).

Photo by Glenn Carstens-Peters on Unsplash

Tabulation (bottom-up approach)

Tabulation is the opposite of memoization and avoids recursion altogether. Problems are solved starting from the solutions of the related subproblems and arriving at the original problem. Implementations of tabulation are always iterative and typically involve filling an n-dimensional table. The solution to the original problem is computed based on the results in the table. Tabulation is preferred if the original problem requires all subproblems to be solved (this is due to the absence of recursion and the use of an array as opposed to something like a hash map).

The FAST Method

The FAST Method is a four-step process for determining an optimal solution for almost any dynamic programming problem. The four steps are as follows:

• Find the solution first

  • This refers to finding an initial brute-force solution first. Efficiency should not be a concern at this step.

• Analyze the first solution

  • This is the step where we decide whether or not to employ dynamic programming. One way to do so is to analyze the time complexity of the first solution.

• Identify the Subproblems

• Turn the solution around

  • This is the step where we take our recursive solution and attempt to make it into an iterative solution.

  

A strong understanding of DP is invaluable when doing competitive programming.

---