Dynamic programming (DP) is one of the most basic and, at the same time, challenging programming paradigms. Some of the best algorithms that I know, such as the Levenshtein distance and DTW are implemented using this paradigm. It consists of simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner and then using the sub-problems’ precomputed solutions to solve the complicated one.

The key advantage of using DP is that it is fast. There are two key attributes that a problem must have in order for DP to be applicable: optimal substructure and overlapping sub-problems. In this post, I’ll rely on a set of representative DP problems to perform the two basic solution strategies: memoization and tabulation. These problems are presented and explained by Alvin Zablan, in this excellent video that he prepared for freeCodeCamp.org. I have written my own solutions to the problems in Java.

# Strategies

The first indication that we are dealing with a DP problem is noticing overlapping sub-problems. Then, one has to decide what the trivially smallest input is. Depending on the implementation strategy to use, memoization (recursive) or tabulation (iterative), there are recipes that one can follow to address DP problems. For the memoization strategy, the most challenging step is to visualize the problem as a tree. When using the tabulation, finding the proper way to iterate through the table is usually the most challenging task.

### Memoization

1. Make it work
• visualize the problem as a tree (hard)
• implement the tree using recursion
• test it
2. Make it efficient
• add a base case to return memo values
• store return values into the memo

### Tabulation

1. Visualize the problem as a table
2. Size the size of the table based on the inputs
3. Initialize the table with default values
4. Seed the trivial answer into the table
5. Iterate through the table (hard)
6. Fill further positions based on the current position

# Problems

• Fibonacci (“What is the best way to do it?” -> Optimization problem)
• Grid traveler (“How will you do it?” -> Combinatoric problem)
• Can sum (“Can you do it?” -> Decision problem)
• How sum (“How will you do it?” -> Combinatoric problem)
• Best sum (“What is the best way to do it?” -> Optimization problem)
• Can construct (“Can you do it?” -> Decision problem)
• Count construct (“How will you do it?” -> Combinatoric problem)
• All construct (“In how many ways can you do it?” -> Combinatoric problem)

# Fibonacci

Description: Write a function that returns the n-th number of the fibonacci sequence. To generate the next number of the sequence, we sum the previous two. For example, these are the first 10 fibonacci numbers:

n012345678910
fib(n)011235813213455

Example:

# Grid Traveler

Description: You are a traveler on a 2D grid. You begin in the top-left corner and your goal is to travel to the bottom-right corner. You may only move down or right. In how many ways can you travel to the goal on a grid with dimensions `n`*`m`.

Example:

# Can Sum

Description: Write a function that return a boolean indicating whether it is possible to generate a `targetSum` value by adding number from a given array. Elements of the array are positive integers and can be used as many time as needed.

Example:

# How Sum

Description: Write a function that return an array containing any combination of elements that add up to exactly the `targetSum`. If there is no combination that adds up to the `targetSum`, then return `null`.

Example:

# Best Sum

Description: Write a function that returns an array containing the shortest combination of numbers that add up to exactly the `targetSum`. If there is a tie fo the shortest combination, you may return any one of the shortest.

Example:

# Can Construct

Description: Write a function that returns a boolean indication whether the `target` string can be constructed by concatenating elements of the `wordBank` array of strings. Elements in `wordBank` can be reused as many times as needed.

Example:

# Count Construct

Description: Write a function that returns the number of ways that the `target` can be constructed by concatenating elements of the `wordBank` array. Elements in `wordBank` can be reused as many times as needed.

Example:

# All Construct

Description: Write a function that returns a 2D array containing all the ways that the `target` can be constructed by concatenating elements of the `wordBank` array. Each element of the 2D array should represent one combination that constructs the `target`. Elements in `wordBank` can be reused as many times as needed.

Example: