Fibonacci Sequence

The Fibonacci Sequence is a classic example of the Dynamic Programming problem.

The Fibonacci Sequence is the sequence where an element is a sum of two previous elements.

The following is a sample Fibonacci Sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21 and so on.

Let’s denote 𝐹(𝑛) as a function to find 𝑛!" Fibonacci number, then the general equation will be

𝐹(𝑛) = 𝐹(𝑛 − 1) + 𝐹(𝑛 − 2)

0, 𝑖𝑓 𝑛 = 0
𝐹(𝑛) = * 1, 𝑖𝑓 𝑛 = 1
𝐹 (𝑛 − 1) + 𝐹 (𝑛 − 2), 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

Figure 1. The recursive tree formula

for the Fibonacci Sequence.

To find 6!" Fibonacci number, find 5!" and 4!" Fibonacci numbers and sum them up.

𝐹(6) = 𝐹(5) + 𝐹(4)

To find 5!" Fibonacci number, find 4!" and 3#$ Fibonacci numbers and sum them up.

𝐹(5) = 𝐹(4) + 𝐹(3)

To find 4!" Fibonacci number, find 3#$ and 2%$ Fibonacci numbers and sum them up.

𝐹(4) = 𝐹(3) + 𝐹(2)

To find 3#$ Fibonacci number, find 2%$ and 1&! Fibonacci numbers and sum them up.

4
 𝐹(3) = 𝐹(2) + 𝐹(1)

To find 2%$ Fibonacci number, find 1&! and 0 Fibonacci numbers and then sum them up.

𝐹(2) = 𝐹(1) + 𝐹(0)

For 1&! and 0 Fibonacci numbers we already know the values.

𝐹(1) = 1

𝐹(0) = 0

Figure 2. The recursive tree

for the Fibonacci Sequence.

5
Coin Change

Another example of the Dynamic Programming problem is the Coin Change Problem.

Given a target amount and coins of different denominations, find the minimum number of coins to
make the target amount.

Let’s consider the following example

𝑡𝑎𝑟𝑔𝑒𝑡 𝑎𝑚𝑜𝑢𝑛𝑡 = 7
𝑐𝑜𝑖𝑛𝑠 = 1, 3, 5

From the above example, the minimum number of coins to make 7 is three. We can use two coins with
denomination 1 and one coin with denomination 5, so 7 = 5 + 1 + 1 (there is another option to choose
3 + 3 + 1).

Let’s denote 𝐹(𝑛) as a function to find the minimum number of coins to make 𝑛 amount, then the
general equation will be

𝐹(𝑛 − 5)
𝐹(𝑛) = 𝑚𝑖𝑛 <𝐹(𝑛 − 3)? + 1
𝐹 (𝑛 − 1)

0, 𝑛 = 0
𝐹(𝑛) = @
minD𝐹(𝑛 − 5), 𝐹(𝑛 − 3), 𝐹(𝑛 − 1)E + 1, 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

Figure 3. The recursive tree formula

for the Coin Change Problem.

To find the minimum number of coins to make 𝐹(7), we can choose one of the following options:
• use one coin with denomination 5 and remain with new 𝑡𝑎𝑟𝑔𝑒𝑡 𝑎𝑚𝑜𝑢𝑛𝑡 2, 𝐹(2)
• use one coin with denomination 3 and remain with new 𝑡𝑎𝑟𝑔𝑒𝑡 𝑎𝑚𝑜𝑢𝑛𝑡 4, 𝐹(4)
• use one coin with denomination 1 and remain with new 𝑡𝑎𝑟𝑔𝑒𝑡 𝑎𝑚𝑜𝑢𝑛𝑡 6, 𝐹(6)

6
 𝐹(2) (𝑢𝑠𝑒 5)
𝐹(7) = 𝑚𝑖𝑛 * 𝐹(4)(𝑢𝑠𝑒 3) 4 + 1
𝐹(6) (𝑢𝑠𝑒 1)

To make 𝐹(2), choose one of the following options:

• can’t use the coin with denomination 5 (greater than target amount)
• can’t use the coin with denomination 3 (greater than target amount)
• use one coin with denomination 1 and remain with new 𝑡𝑎𝑟𝑔𝑒𝑡 𝑎𝑚𝑜𝑢𝑛𝑡 1, 𝐹(1)

𝑐𝑎𝑛′𝑡 𝑢𝑠𝑒 5 𝑜𝑟 3
𝐹(2) = 𝑚𝑖𝑛 6 = + 1
𝐹(1) (𝑢𝑠𝑒 1)

To make 𝐹(1), choose one of the following options:

• can’t use the coin with denomination 5 (greater than target amount)
• can’t use the coin with denomination 3 (greater than target amount)
• use one coin with denomination 1 and remain with new 𝑡𝑎𝑟𝑔𝑒𝑡 𝑎𝑚𝑜𝑢𝑛𝑡 0, 𝐹(0)

𝑐𝑎𝑛′𝑡 𝑢𝑠𝑒 5 𝑜𝑟 3
𝐹(1) = 𝑚𝑖𝑛 6 = + 1
𝐹(0) (𝑢𝑠𝑒 1)

𝑐𝑎𝑛′𝑡 𝑢𝑠𝑒 5
𝐹(4) = 𝑚𝑖𝑛 * 𝐹(1) 4 + 1
𝐹(3)

𝑐𝑎𝑛′𝑡 𝑢𝑠𝑒 5 𝑜𝑟 3
𝐹(1) = 𝑚𝑖𝑛 6 = + 1
𝐹(0) (𝑢𝑠𝑒 1)

𝑐𝑎𝑛′𝑡 𝑢𝑠𝑒 5
𝐹(3) = 𝑚𝑖𝑛 * 𝐹(0) 4 + 1
𝐹(2)

𝑐𝑎𝑛′𝑡 𝑢𝑠𝑒 5 𝑜𝑟 3
𝐹(2) = 𝑚𝑖𝑛 6 = + 1
𝐹(1)

𝑐𝑎𝑛′𝑡 𝑢𝑠𝑒 5 𝑜𝑟 3
𝐹(1) = 𝑚𝑖𝑛 6 = + 1
𝐹(0)

𝐹(1)
𝐹(6) = 𝑚𝑖𝑛 *𝐹(3)4 + 1
𝐹(5)

𝑐𝑎𝑛′𝑡 𝑢𝑠𝑒 5 𝑜𝑟 3
𝐹(1) = 𝑚𝑖𝑛 6 = + 1
𝐹(0)

7
 𝑐𝑎𝑛′𝑡 𝑢𝑠𝑒 5
𝐹(3) = 𝑚𝑖𝑛 * 𝐹(0) 4 + 1
𝐹(2)

𝑐𝑎𝑛′𝑡 𝑢𝑠𝑒 5 𝑜𝑟 3
𝐹(2) = 𝑚𝑖𝑛 6 = + 1
𝐹(1)

𝑐𝑎𝑛′𝑡 𝑢𝑠𝑒 5 𝑜𝑟 3
𝐹(1) = 𝑚𝑖𝑛 6 = + 1
𝐹(0)
𝐹(0)
𝐹(5) = 𝑚𝑖𝑛 *𝐹(2)4 + 1
𝐹(4)

𝑐𝑎𝑛′𝑡 𝑢𝑠𝑒 5 𝑜𝑟 3
𝐹(2) = 𝑚𝑖𝑛 6 = + 1
𝐹(1)

𝑐𝑎𝑛′𝑡 𝑢𝑠𝑒 5 𝑜𝑟 3
𝐹(1) = 𝑚𝑖𝑛 6 = + 1
𝐹(0)

𝑐𝑎𝑛′𝑡 𝑢𝑠𝑒 5
𝐹(4) = 𝑚𝑖𝑛 * 𝐹(1) 4 + 1
𝐹(3)

𝑐𝑎𝑛′𝑡 𝑢𝑠𝑒 5 𝑜𝑟 3
𝐹(1) = 𝑚𝑖𝑛 6 = + 1
𝐹(0)

𝑐𝑎𝑛′𝑡 𝑢𝑠𝑒 5
𝐹(3) = 𝑚𝑖𝑛 * 𝐹(0) 4 + 1
𝐹(2)

𝑐𝑎𝑛′𝑡 𝑢𝑠𝑒 5 𝑜𝑟 3
𝐹(2) = 𝑚𝑖𝑛 6 = + 1
𝐹(1)

𝑐𝑎𝑛′𝑡 𝑢𝑠𝑒 5 𝑜𝑟 3
𝐹(1) = 𝑚𝑖𝑛 6 = + 1
𝐹(0)

𝐹(0) = 0

8
Figure 4. The recursive tree
for the Coin Change Problem.

9
Unique Paths

Given a 2D grid, find the total number of unique paths from the top-left (0,0) corner to the bottom-
right corner (𝑛 − 1, 𝑚 − 1), where 𝑛 is the number of rows and 𝑚 is the number of columns.

Let’s denote 𝐹(𝑥, 𝑦) as a function to find the total number of unique paths to reach a position (𝑥, 𝑦),
then the general equation will be

𝐹(𝑥, 𝑦) = 𝐹(𝑥 − 1, 𝑦) + 𝐹(𝑥, 𝑦 − 1)

1, 𝑥 = 0 𝑎𝑛𝑑 𝑦 = 0
𝐹(𝑥, 𝑦) = @
𝐹 (𝑥 − 1, 𝑦) + 𝐹 (𝑥, 𝑦 − 1), 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

Figure 5. General recursive tree

for the Coin Change Problem.

For 𝑛 = 3 and 𝑚 = 3,

From position (2,2) we can go:

• up (1,2)
• left (2,1)

𝐹(2,2) = 𝐹(1,2) + 𝐹(2,1)

From position (1,2) we can go:
• up (0,2)
• left (1,1)

𝐹(1,2) = 𝐹(0,2) + 𝐹(1,1)

From position (0,2) we can go:

• only left (0,1)

𝐹(0,2) = 𝐹(0,1)

From position (0, 1) we can go:

• only left (0,0)

10
 𝐹(0,1) = 𝐹(0,0)

𝐹(2, 1) = 𝐹(1, 1) + 𝐹(2, 0)

𝐹(1, 1) = 𝐹(0, 1) + 𝐹(1, 0)

𝐹(0, 1) = 𝐹(0, 0)

𝐹(1, 0) = 𝐹(0, 0)

𝐹(2, 0) = 𝐹(1, 0)

𝐹(1, 0) = 𝐹(0, 0)

𝐹(0,0) = 1

Figure 6. The recursive tree for Unique Paths.

From the recursive trees, we can see that the problem in the solutions above is the recalculation of the
same sub-problems (states) multiple times, which leads to unnecessary extra work.

11
How does Dynamic Programming help us to solve this problem?

Dynamic Programming breaks a problem into sub-problems (states) and finds the most optimal
solutions for all sub-problems. To avoid repetitive calculations, it caches already calculated solutions.
Then based on solutions for sub-problems, it builds the solution for the general problem.

12
How to solve Dynamic Programming Problems
Dynamic Programming problems can be categorized into optimization and combinatorial problems.
Optimization problems require finding the most optimal solution, such as the
minimum/maximum/shortest/longest answer, while combinatorial problems require finding a number
of ways/the probability of performing some operation.

In Computer Programming, there are two methods to solve Dynamic Programming problems:
• Top-Down (recursive)
• Bottom-Up (iterative)

Top-Down

The top-down approach solves a problem recursively, going from a target state to a base case and
breaking the problem into sub-problems (states). Then it finds an optimal solution for every sub-
problem and stores a result for reuse in the future.

Figure 7. The top-down approach.

13
How to come up with a recursive solution
Perform the following steps to understand how to come up with a recursive solution.

Step 1. Iterate Over Options

When we solve a problem recursively, for every sub-problem (state), we have different options
(directions) to choose to reach our target. We need to iterate over all possible options to find the
most optimal solution.

𝐹(𝑜𝑝𝑡𝑖𝑜𝑛 1)
𝐹(𝑛) → 𝐹(𝑜𝑝𝑡𝑖𝑜𝑛 1)
…
𝐹(𝑜𝑝𝑡𝑖𝑜𝑛 𝑘)
Fibonacci Sequence

𝐹(𝑙𝑎𝑠𝑡 𝑡𝑒𝑟𝑚)
𝐹(𝑐𝑢𝑟𝑟𝑒𝑛𝑡 𝑡𝑒𝑟𝑚) →
𝐹(𝑜𝑛𝑒 𝑏𝑒𝑓𝑜𝑟𝑒 𝑡ℎ𝑒 𝑙𝑎𝑠𝑡 𝑡𝑒𝑟𝑚)

There are two options to choose to obtain 𝑛!" term:

• the last term
• one before the last term

Coin Change Problem

𝐹(𝑢𝑠𝑒 𝑐𝑜𝑖𝑛 𝑤𝑖𝑡ℎ 𝑑𝑒𝑛𝑜𝑚𝑖𝑛𝑎𝑡𝑖𝑜𝑛 5)

𝐹(𝑡𝑎𝑟𝑔𝑒𝑡) → 𝐹 (𝑢𝑠𝑒 𝑐𝑜𝑖𝑛 𝑤𝑖𝑡ℎ 𝑑𝑒𝑛𝑜𝑚𝑖𝑛𝑎𝑡𝑖𝑜𝑛 3)
𝐹(𝑢𝑠𝑒 𝑐𝑜𝑖𝑛 𝑤𝑖𝑡ℎ 𝑑𝑒𝑛𝑜𝑚𝑖𝑛𝑎𝑡𝑖𝑜𝑛 1)

There are three options to choose to make the target amount:

• use the coin with denomination 5
• use the coin with denomination 3
• use the coin with denomination 1

Unique Paths

𝐹(𝑚𝑜𝑣𝑒 𝑢𝑝)
𝐹(𝑥, 𝑦) →
𝐹(𝑚𝑜𝑣𝑒 𝑙𝑒𝑓𝑡)

There are two options (directions) to choose to reach the target position:
• move up
• move left

14
Step 2. Reduce Target
Choosing every option, we reduce a target to a particular value, and we call a recursive function
again with the new updated target.

Fibonacci Sequence

𝐹(𝑛 − 1)
𝐹(𝑛) →
𝐹(𝑛 − 2)

• Choosing the last term 𝐹(𝑛 − 1) reduces the problem to find (𝑛 − 1)!" term.
• Choosing the one before the last term 𝐹(𝑛 − 2) reduces the problem to find (𝑛 − 2)!" term.

𝐹(1)
𝐹(2) →
𝐹(0)

Coin Change Problem

𝐹(𝑡𝑎𝑟𝑔𝑒𝑡 − 5)
𝐹(𝑡𝑎𝑟𝑔𝑒𝑡) → 𝐹(𝑡𝑎𝑟𝑔𝑒𝑡 − 3)
𝐹(𝑡𝑎𝑟𝑔𝑒𝑡 − 1)

• Choosing the coin with denomination 5 reduces the problem to make the new target amount of
𝑡𝑎𝑟𝑔𝑒𝑡 − 5.
• Choosing the coin with denomination 3 reduces the problem to make the new target amount of
𝑡𝑎𝑟𝑔𝑒𝑡 − 3.
• Choosing the coin with denomination 1 reduces the problem to make the new target amount of
𝑡𝑎𝑟𝑔𝑒𝑡 − 1.

𝐹(11 − 5)
𝐹(11) → 𝐹 (11 − 3)
𝐹(11 − 1)
𝐹(6)
𝐹(11) → 𝐹 (8)
𝐹(10)

Unique Paths

15
 𝐹(𝑥 − 1, 𝑦)
𝐹(𝑥, 𝑦) →
𝐹(𝑥, 𝑦 − 1)

• Choosing the option to move up reduces the problem to find the number of unique paths to
reach (𝑥 − 1, 𝑦).
• Choosing the option to move left reduces the problem to find the number of unique paths to
reach (𝑥, 𝑦 − 1).

𝐹(1,2)
𝐹(2,2) →
𝐹(2,1)

Step 3. Choose Optimal Solution

After coming from recursive calls, we choose an optimal solution among these calls and add the
value for the current state.

Fibonacci Sequence

Sum up two previous values.

𝐹(𝑛) = 𝐹(𝑛 − 1) + 𝐹(𝑛 − 2)

Coin Change Problem

Choose the option that leads to the most optimal solution and add one to use one coin for the current
state.

𝐹(𝑡𝑎𝑟𝑔𝑒𝑡 − 5)
𝐹(𝑡𝑎𝑟𝑔𝑒𝑡) = 𝑚𝑖𝑛 <𝐹(𝑡𝑎𝑟𝑔𝑒𝑡 − 3)? + 1
𝐹(𝑡𝑎𝑟𝑔𝑒𝑡 − 1)

Unique Paths

Sum up both options to find the total number of distinct ways.

𝐹(𝑥, 𝑦) = 𝐹(𝑥 − 1, 𝑦) + 𝐹(𝑥, 𝑦 − 1)

16
 Step 4. Base Case
When we reach a base case, we need to quit a recursive function. The base case can be a base state
or case when a sub-problem is no longer valid (in this case, when it returns the worst result).

Fibonacci Sequence

We already know that the first two Fibonacci numbers are 0 and 1 respectively.

𝐹(1) = 1

𝐹(0) = 0

1 int F(n) {
2 if (n == 0) {
3 // base case
4 }
5 if (n == 1) {
6 // base case
7 }
8 }

Coin Change

When 𝑡𝑎𝑟𝑔𝑒𝑡 equals 0 (we don’t need any coin to make 0) or less than 0, the function reaches the
base case.

𝐹(0) = 0

1 int F(target) {
2 if (target == 0) {
3 // base case
4 }
5 if (target < 0) {
6 // not valid
7 }
8 }

Unique Paths

When the position equals the destination cell or the position is out of bounds, the function reaches the
base case.

𝐹(0, 0) = 1

17
 1 int F(x, y) {
2 if (x == 0 && y == 0) {
3 // base case
4 }
5 if (x < 0 || y < 0) {
6 // not valid
7 }
8 }

Step 5. Return Result

Return a result of a recursive function.

After reaching the end of a function, return a result.

return result

Applying the steps above to solve examples recursively

Recursive solution for the Fibonacci Sequence

1 int Fib(int n) {
2 if (n == 0) {
3 return 0; // step 4
4 }
5 if (n == 1) {
6 return 1; // step 4
7 }
8
9 int last = Fib(n-1); // step 1 & 2
10 int beforeLast = Fib(n-2); // step 1 & 2
11 int result = last + beforeLast; // step 3
12
13 return result; // step 5
14 }

Recursive solution for Coin Change Problem

1 int CoinChange(int target, vector<int> &coins) {

2 if (target == 0) {
3 return 0; // step 4
4 }
5 int result = inf;
6 for (int i = 0; i < coins.size(); ++i) { // step 1

18
7 if (coins[i] <= target) {
8 int substateSolution = CoinChange(target-coins[i], coins); // step 2
9 result = min(result, substateSolution+1); // step 3
10 }
11 }
12 return result; // step 5
13 }

Recursive solution for Unique Paths

1 int UniquePaths(int x, int y) {

2 if (x == 0 && y == 0) {
3 return 1; // step 4
4 }
5 if (x < 0 || y < 0) {
6 return 0; // step 4
7 }
8 int up = UniquePaths(x-1, y); // step 1 & 2
9 int left = UniquePaths(x, y-1); // step 1 & 2
10
11 int result = up + left; // step 3
12
13 return result; // step 5
14 }

The problem with these recursive solutions is the recalculation of sub-problems, which leads to slow
performance.

19
How to calculate the time complexity of a recursive solution
To calculate the time-complexity of a recursive solution, try to answer the following questions:
• How many times does a function call itself (𝑡)?
• How many times is a function being recursed (𝑘)?

Based on that, we can say that the time complexity of a plain recursive solution is exponential 𝑂(𝑡 ' ).

If we draw a recursive tree, we can find the time complexity by summing up the number of nodes in
the tree.

Figure 8. The recursive tree.

Fibonacci Sequence

To find 𝑛!" Fibonacci number, we need to sum up two previous Fibonacci numbers.

𝐹(𝑛) = 𝐹(𝑛 − 1) + 𝐹(𝑛 − 2)

The function is being called two times:

• 𝐹(𝑛 − 1)
• 𝐹(𝑛 − 2)

Then it’s being recursed 𝑛 times from 𝑛 to 0, where 𝑛 is the depth of the recursive tree for the
function.

So, the time complexity of the plain recursive solution is 𝑂(2% ).

Let’s calculate the time complexity of the function to see if the statement above is true.

Let’s denote 𝑇(𝑛) as a function to calculate the time complexity of the Fibonacci Sequence.

20
 𝑇(𝑛) = 𝑇(𝑛 − 1) + 𝑇(𝑛 − 2) + 𝐶 ,

where 𝑇(𝑛 − 1) and 𝑇(𝑛 − 2) are the time complexities to find 𝑛 − 1!" Fibonacci and 𝑛 − 2!" Fibonacci
numbers respectively, and 𝐶 is the number of constant operations performed inside the recursive call.

For simplicity let’s assume that 𝑇(𝑛 − 2) ≤ 𝑇(𝑛 − 1).

𝑇(𝑛) = 2 × 𝑇(𝑛 − 1) + 𝐶

𝑇(𝑛 − 1) = 2 × 𝑇(𝑛 − 2) + 𝐶

𝑇(𝑛) = 2 × (2 × 𝑇(𝑛 − 2) + 𝐶) + 𝐶

𝑇(𝑛) = 22 × 𝑇(𝑛 − 2) + 3𝐶

𝑇(𝑛 − 2) = 2 × 𝑇(𝑛 − 3) + 𝐶

𝑇(𝑛) = 22 × (2 × 𝑇(𝑛 − 3) + 𝐶) + 3𝐶

𝑇(𝑛) = 23 × 𝑇(𝑛 − 3) + 7𝐶

𝑇(𝑛) = 2' × 𝑇(𝑛 − 𝑘) + (2' − 1) × 𝐶

𝑇(0) = 1

𝑛−𝑘 = 0

𝑛 = 𝑘

𝑇(𝑛) = 2% × 𝑇(0) + (2% − 1) × 𝐶 = 2% + (2% − 1) × 𝐶

The upper bound time complexity is 𝑂(2% ).

Using the idea that 𝐹(𝑛) and 𝑇(𝑛) are calculated in the same way, we can find a tighter upper bound
time complexity. Approximate value for 𝐹(𝑛) is 𝑂(𝜙 % ), where 𝜙 = (1 + √5)/2 ≈ 1.618.

Consequently,

𝑇(𝑛) = 𝑂(𝜙 % ) = 𝑂((1 + √5)/2)% ) = 𝑂(1.618% )

21
Coin Change

The function is being called 𝑛 times:

• 𝐹(𝑡𝑎𝑟𝑔𝑒𝑡 − 𝑐𝑜𝑖𝑛 1)
• 𝐹(𝑡𝑎𝑟𝑔𝑒𝑡 − 𝑐𝑜𝑖𝑛 2)
• 𝐹(𝑡𝑎𝑟𝑔𝑒𝑡 − 𝑐𝑜𝑖𝑛 3)
• …
• 𝐹(𝑡𝑎𝑟𝑔𝑒𝑡 − 𝑐𝑜𝑖𝑛 𝑛)

where 𝑛 is the number of coins.

Then it’s being recursed 𝑡𝑎𝑟𝑔𝑒𝑡 𝑎𝑚𝑜𝑢𝑛𝑡 times (worst case).

So, the time complexity of the plain recursive solution is 𝑂(𝑛!(#)*! (,-.%! ).

Unique Paths

The function is being called two times:

• 𝐹(𝑥 − 1, 𝑦)
• 𝐹(𝑥, 𝑦 − 1)

Then it’s being recursed 𝑛 + 𝑚 times, where 𝑛 is the number of rows and 𝑚 is the number of columns.

Why is the function being recursed 𝑛 + 𝑚 times?

For every recursive call, we move one step up, or one step left. In other words, to reach leaf nodes, we
need to exhaust total rows and total columns, meaning that the depth of our recursive tree will be 𝑛 +
𝑚.

22
 Figure 9. The recursive tree for Unique Paths.

So, the time complexity of the plain recursive solution is 𝑂(2%/, ) ≈ 𝑂(2% )..

All the recursive solutions above lead to exponential time complexity due to overlapping sub-
problems.

Memoization

How to optimize the recursive solutions above

A recursive solution has overlapping sub-problems that are being calculated several times. To avoid
repetitive calculations, we need to store already calculated solutions for sub-problems. Next time, we
will also need to use stored values instead of a recalculation. This technique is called memoization.

How to derive keys for memoization

To understand how sub-problem solutions are stored, we need to know the keys for the memoization
table. According to The Theory of Dynamic Programming, we have state parameters (or state
variables) that determine each state. These parameters transform each state.

23
 “We have a physical system whose state at any time is determined by a set of quantities which we
call state parameters, or state variables (The Theory of Dynamic Programming, Richard Bellman).”

“These decisions are equivalent to transformations of the state variables, the choice of a decision
being identical with the choice of a transformation. The outcome of the preceding decisions is to
be used to guide the choice of future ones, with the purpose of the whole process of maximizing
some function of the parameters describing the final state (The Theory of Dynamic Programming,
Richard Bellman).”

The statements above give an idea to use state parameters to store information about a particular
state’s decision.

memo defines our storage for sub-problem solutions.

Fibonacci Sequence

Let’s have a look at the recursive solution again.

1 int Fib(int n) {
2 if (n == 0) {
3 return 0; // base case
4 }
5 if (n == 1) {
6 return 1; // base case
7 }
8 return Fib(n-1) + Fib(n-2);
9 }

For the Fibonacci Sequence, each state 𝐹𝑖𝑏(𝑖𝑛𝑡 𝑛) has the term number 𝑛 as a parameter,
transforming each state. Based on this information, we can use the parameter 𝑛 as the key for the
memoization table.

1 int Fib(int n) {
2 if (n == 0) {
3 return 0; // base case
4 }
5 if (n == 1) {
6 return 1; // base case
7 }
8 if (memo[n] != -1) { // check if a state was already calculated

24
9 return memo[n];
10 }
11 memo[n] = Fib(n-1) + Fib(n-2); // store calculations
12 return memo[n];
13 }

Coin Change

The parameter 𝑡𝑎𝑟𝑔𝑒𝑡 transforms each state, and we can use it as the key for the memoization table.

1 int CoinChange(int target, vector<int> &coins) {

2 if (target == 0) {
3 return 0; // base case
4 }
5
6 int result = inf;
7
8 for (int i = 0; i < coins.size(); ++i) {
9 if (coins[i] <= target) { // check validity of a sub-problem
10 result = min(result, CoinChange(target - coins[i], coins) + 1);
11 }
12 }
13
14 return result;
15 }

Consequently,

1 int CoinChange(int target, vector<int> &coins) {

2 if (target == 0) {
3 return 0; // base case
4 }
5
6 if (memo[target] != -1) { // check if a state was already calculated
7 return memo[target];
8 }
9
10 int result = inf;
11
12 for (int i = 0; i < coins.size(); ++i) {
13 if (coins[i] <= target) { // check validity of a sub-problem
14 result = min(result, CoinChange(target - coins[i], coins) + 1);
15 }
16 }
17

25
18 memo[target] = result;
19
20 return result;
21 }

Unique Paths

There are two state parameters 𝑥 and 𝑦, which we can use as the keys for the memoization table.

1 int UniquePaths(int x, int y) {

2 if (x == 0 && y == 0) {
3 return 1; // base case
4 }
5 if (x < 0 || y < 0) {
6 return 0; // not valid sub-problem
7 }
8 return UniquePaths(x-1, y) + UniquePaths(x, y-1);
9 }

The solution with memoization.

1 int UniquePaths(int x, int y) {

2 if (x == 0 && y == 0) {
3 return 1; // base case
4 }
5 if (x < 0 || y < 0) {
6 return 0; // not valid sub-problem
7 }
8 if (memo[x][y] != -1) { // check if a state was already calculated
9 return memo[x][y];
10 }
11 memo[x][y] = UniquePaths(x-1, y) + UniquePaths(x, y-1);
12 return memo[x][y];
13 }

In the case above, we define a 2-dimensional array to store sub-state information.

How to calculate the time complexity of a recursive solution with memoization

To calculate the time-complexity of a recursive solution with memoization, try to answer the following
questions:
• How many states do we have in total? (𝑁)?
• How many times does a function call itself? (𝑡)?

26
The only difference is the fact that memoization will help us to avoid repetitive calculations for sub-
problems. As a result, the time complexity will be 𝑂(𝑁𝑡).

Fibonacci Sequence

1 int Fib(int n) {
2
3 /*base cases*/
4
5 if (memo[n] != -1) {
6 return memo[n]; // check if a state was already calculated
7 }
8 memo[n] = Fib(n-1) + Fib(n-2); // store calculations
9 return memo[n];
10 }

The function is being called two times:

• 𝐹(𝑛 − 1)
• 𝐹(𝑛 − 2)

We have a total number of 𝑛 states. The time complexity of the recursive solution with memoization is
𝑂(𝑛).

Coin Change

1 int CoinChange(int target, vector<int> &coins) {

2
3 /*base cases*/
4
5 if (memo[target] != -1) {
6 return memo[target];
7 }
8
9 int result = inf;
10
11 for (int i = 0; i < coins.size(); ++i) {
12 if (coins[i] <= target) { // check validity of a sub-problem
13 result = min(result, CoinChange(target - coins[i], coins) + 1);
14 }
15 }
16 memo[target] = result;
17
18 return result;

27
19 }

The function is being called 𝑛 times:

• 𝐹(𝑡𝑎𝑟𝑔𝑒𝑡 − 𝑐𝑜𝑖𝑛 1)
• 𝐹(𝑡𝑎𝑟𝑔𝑒𝑡 − 𝑐𝑜𝑖𝑛 2)
• 𝐹(𝑡𝑎𝑟𝑔𝑒𝑡 − 𝑐𝑜𝑖𝑛 3)
• ...
• 𝐹(𝑡𝑎𝑟𝑔𝑒𝑡 − 𝑐𝑜𝑖𝑛 𝑛)

where 𝑛 is the number of coins.

Here we have a total number of 𝑡𝑎𝑟𝑔𝑒𝑡 𝑎𝑚𝑜𝑢𝑛𝑡 states. The time complexity of the recursive solution
with memoization is 𝑂(𝑡𝑎𝑟𝑔𝑒𝑡 𝑎𝑚𝑜𝑢𝑛𝑡 × 𝑛).

Unique Paths

1 int UniquePaths(int x, int y) {

2 /*base cases*/
3
4 if (memo[x][y] != -1) {
5 return memo[x][y];
6 }
7 memo[x][y] = UniquePaths(x-1, y) + UniquePaths(x, y-1);
8 return memo[x][y];
9 }

The function is being called two times:

• 𝐹(𝑥 − 1, 𝑦)
• 𝐹(𝑥, 𝑦 − 1)

We have a total of 𝑛𝑚 states. The time complexity of the recursive solution with memoization is 𝑂(𝑛𝑚).

28
Bottom-Up

The bottom-up approach solves a problem iteratively, going from a base case towards a target state.
The bottom-up method finds an optimal solution for each sub-problem and stores a result for each
sub-problem for later use. There are two ways of solving problems iteratively: backward style and
forward style.

Backward Style

In the backward style iteration, we calculate a solution for the current state based on solutions of the
previous states.

𝑓(𝑖) = 𝑓(𝑖 − 1) + 𝑓(𝑖 − 2)

Fibonacci Sequence

table[i] = table[i-1] + table[i-2]

Forward Style

In the forward style iteration, we calculate a solution for the next state based on solutions of the
current state.

𝑓(𝑖 + 1) = 𝑓(𝑖) + 𝑓(𝑖 − 1)

Fibonacci Sequence

table[i+1] = table[i] + table[i-1]

Figure 10. The bottom-up approach.

29
How to come up with an iterative solution

Perform the following steps to understand how to come up with an iterative solution.

table refers to a table to store sub-problem solutions.

Step 1. Base Case

Find a base case for a given problem.

The base case can be a state we already know or can calculate the answer.

Fibonacci Sequence

We already know that the first two Fibonacci numbers are 0 and 1 respectively.

𝑡𝑎𝑏𝑙𝑒(0) = 0

𝑡𝑎𝑏𝑙𝑒(1) = 1

Coin Change

We don’t need any coins to make the total amount of 0.

𝑡𝑎𝑏𝑙𝑒(0) = 0

Unique Paths

We are using zero-indexed positions, and we have only one path to reach (0, 0) position.

𝑡𝑎𝑏𝑙𝑒(0, 0) = 1

Step 2. Move Toward a Target State

Starting from a base case, we move toward a target state.

Fibonacci Sequence

𝑡𝑎𝑏𝑙𝑒(0) = 0

𝑡𝑎𝑏𝑙𝑒(1) = 1

𝑡𝑎𝑏𝑙𝑒(2) = . ..

𝑡𝑎𝑏𝑙𝑒(𝑛) = . ..

30
Coin Change

𝑡𝑎𝑏𝑙𝑒(0) = 0

𝑡𝑎𝑏𝑙𝑒(1) = 1

𝑡𝑎𝑏𝑙𝑒(2) = . ..

𝑡𝑎𝑏𝑙𝑒(𝑡𝑎𝑟𝑔𝑒𝑡) = . ..

Unique Paths

𝑡𝑎𝑏𝑙𝑒(0, 0) = 1

𝑡𝑎𝑏𝑙𝑒(0, 1) = . ..

𝑡𝑎𝑏𝑙𝑒(0, 2) = . ..

𝑡𝑎𝑏𝑙𝑒(1, 1) = . ..

𝑡𝑎𝑏𝑙𝑒(𝑥, 𝑦) = . ..

Step 3. Iterate Over Options

For every step (state), we have several options (ways) to choose to come to the current state. We
need to iterate all possible options to find the most optimal solution for the current state.

Fibonacci Sequence

𝑡𝑎𝑏𝑙𝑒(𝑛 − 1)
𝑡𝑎𝑏𝑙𝑒(𝑛) →
𝑡𝑎𝑏𝑙𝑒(𝑛 − 2)

To obtain 𝑛!" term there are two options to come from to the current state:
• the last term 𝑛 − 1
• one before the last term 𝑛 − 2

Coin Change

𝑡𝑎𝑏𝑙𝑒(𝑡𝑎𝑟𝑔𝑒𝑡 − 𝑐𝑜𝑖𝑛 𝑤𝑖𝑡ℎ 𝑑𝑒𝑛𝑜𝑚𝑖𝑛𝑎𝑡𝑖𝑜𝑛 5)

𝑡𝑎𝑏𝑙𝑒(𝑡𝑎𝑟𝑔𝑒𝑡) → 𝑡𝑎𝑏𝑙𝑒(𝑡𝑎𝑟𝑔𝑒𝑡 − 𝑐𝑜𝑖𝑛 𝑤𝑖𝑡ℎ 𝑑𝑒𝑛𝑜𝑚𝑖𝑛𝑎𝑡𝑖𝑜𝑛 3)
𝑡𝑎𝑏𝑙𝑒(𝑡𝑎𝑟𝑔𝑒𝑡 − 𝑐𝑜𝑖𝑛 𝑤𝑖𝑡ℎ 𝑑𝑒𝑛𝑜𝑚𝑖𝑛𝑎𝑡𝑖𝑜𝑛 1)

31
To make the 𝑡𝑎𝑟𝑔𝑒𝑡 𝑎𝑚𝑜𝑢𝑛𝑡, there are three options to come from to the current state:
• using a coin with denomination 5
• using a coin with denomination 3
• using a coin with denomination 1

We are starting from the base case to apply a coin with denomination 𝐾 check if the current target is
greater or equal to the coin denomination.

Unique Paths

𝑡𝑎𝑏𝑙𝑒(𝑥 − 1, 𝑦)
𝑡𝑎𝑏𝑙𝑒(𝑥, 𝑦) →
𝑡𝑎𝑏𝑙𝑒(𝑥, 𝑦 − 1)

To reach the target, there are two options (directions) to come from to the current state:
• from top 𝑥 − 1
• from left 𝑦 − 1

Step 4. Choose an Optimal Solution

We find an optimal solution (maximum, minimum, shortest, longest, etc.) without the current state
and add a value for the current state.

Fibonacci Sequence

𝑡𝑎𝑏𝑙𝑒(𝑛) = 𝑡𝑎𝑏𝑙𝑒(𝑛 − 1) + 𝑡𝑎𝑏𝑙𝑒(𝑛 − 2)

Sum up two previous values.

Coin Change

𝑡𝑎𝑏𝑙𝑒(𝑡𝑎𝑟𝑔𝑒𝑡 − 𝑐𝑜𝑖𝑛 𝑤𝑖𝑡ℎ 𝑑𝑒𝑛𝑜𝑚𝑖𝑛𝑎𝑡𝑖𝑜𝑛 5)

𝑡𝑎𝑏𝑙𝑒(𝑡𝑎𝑟𝑔𝑒𝑡) = 𝑚𝑖𝑛 < 𝑡𝑎𝑏𝑙𝑒(𝑡𝑎𝑟𝑔𝑒𝑡 − 𝑐𝑜𝑖𝑛 𝑤𝑖𝑡ℎ 𝑑𝑒𝑛𝑜𝑚𝑖𝑛𝑎𝑡𝑖𝑜𝑛 3) ? + 1
𝑡𝑎𝑏𝑙𝑒(𝑡𝑎𝑟𝑔𝑒𝑡 − 𝑐𝑜𝑖𝑛 𝑤𝑖𝑡ℎ 𝑑𝑒𝑛𝑜𝑚𝑖𝑛𝑎𝑡𝑖𝑜𝑛 1)

Find an optimal solution without the current state and add one coin for the current state.

Unique Paths

𝑡𝑎𝑏𝑙𝑒(𝑥, 𝑦) = 𝑡𝑎𝑏𝑙𝑒(𝑥 − 1, 𝑦) + 𝑡𝑎𝑏𝑙𝑒(𝑥, 𝑦 − 1)

Sum up both options to find a total path.

32
 Step 5. Return Result
After reaching a target state, return an answer for the target state.

Fibonacci Sequence

𝑟𝑒𝑡𝑢𝑟𝑛 𝑡𝑎𝑏𝑙𝑒(𝑛)

Coin Change

𝑟𝑒𝑡𝑢𝑟𝑛 𝑡𝑎𝑏𝑙𝑒(𝑡𝑎𝑟𝑔𝑒𝑡)

Unique Paths

𝑟𝑒𝑡𝑢𝑟𝑛 𝑡𝑎𝑏𝑙𝑒(𝑥, 𝑦)

Applying the methods above to solve examples iteratively

Iterative solution for the Fibonacci Sequence

1 int Fib(int n) {
2 vector<int> table(n+1);
3
4 table[0] = 0; // step 1
5 table[1] = 1; // step 1
6
7 for (int i = 2; i <= n; ++i) { // step 2
8 int last = table[i-1]; // step 3
9 int beforeLast = table[i-2]; // step 3
8 table[i] = last + beforeLast; // step 4
9 }
10
11 return table[n]; // step 5
12 }

Iterative solution for Coin Change Problem

1 int CoinChange(int target, vector<int> &coins) {

2 vector<int> table(target+1, inf);
3
4 table[0] = 0; // step 1
5
6 for (int i = 1; i <= target; ++i) { // step 2
7 for (int j = 0; j < coins.size(); ++j) { // step 3
8 if (coins[j] <= i) {
9 table[i] = min(table[i], table[i - coins[j]] + 1); // step 4

33
10 }
11 }
12 }
13
14 return table[target] == inf ? -1 : table[target]; // step 5
15 }

Iterative solution for Unique Paths

1 int UniquePaths(int x, int y) {

2 int table[x][y];
3
4 table[0][0] = 1; // step 1
5
6 for (int i = 0; i < x; ++i) { // step 2
7 for (int j = 0; j < y; ++j) { // step 2
8 if (i > 0 && j > 0) {
9 table[i][j] = table[i-1][j] + table[i][j-1]; // step 3 & 4
10 } else if (i > 0) {
11 table[i][j] = table[i-1][j]; // step 3 & 4
12 } else if (j > 0) {
13 table[i][j] = table[i][j-1]; // step 3 & 4
14 }
15 }
16 }
17
18 return table[x-1][y-1]; // // step 5
19 }

How to calculate the time complexity of the iterative solution

To calculate the time complexity of the iterative solution, we need to count how many operations we
are performing inside the function.

Fibonacci Sequence

To find 𝑛!" Fibonacci number, we need to iterate over all Fibonacci numbers till 𝑛!" term. Inside the
single loop, we are performing constant operations 𝑂(1). Time complexity is 𝑂(𝑛).

1 int Fib(int n) {
2
3 /*code*/
4
5 for (int i = 2; i <= n; ++i) {

34
6 table[i] = table[i-1] + table[i-2];
7 }
8
9 return table[n];
10 }

Coin Change

To find the minimum number of coins to make 𝑡𝑎𝑟𝑔𝑒𝑡 𝑎𝑚𝑜𝑢𝑛𝑡, we need to iterate over all options for
every target. Inside the nested loop, we are performing constant operations 𝑂(1). The time complexity
is 𝑂(𝑡𝑎𝑟𝑔𝑒𝑡 𝑎𝑚𝑜𝑢𝑛𝑡 ∗ 𝑛), where 𝑛 is the number of coins.

1 int CoinChange(int target, vector<int> &coins) {

2
3 /* code */
4
5 for (int i = 1; i <= target; ++i) {
6 for (int j = 0; j < coins.size(); ++j) {
7 if (coins[j] <= i) {
8 table[i] = min(table[i], table[i - coins[j]] + 1);
9 }
10 }
11 }
12
13 return table[target] == inf ? -1 : table[target];
14 }

Unique Paths

To reach the target position, we need to iterate over all positions and sum up unique paths. The time
complexity is 𝑂(𝑛𝑚).

1 int UniquePaths(int x, int y) {

2
3 /* code */
4
5 for (int i = 0; i < x; ++i) { // iterate over rows
6 for (int j = 0; j < y; ++j) { // iterate over columns
7 if (i > 0 && j > 0) {
8 table[i][j] = table[i-1][j] + table[i][j-1]; // choose options
9 } else if (i > 0) {
10 table[i][j] = table[i-1][j]; // choose options
11 } else if (j > 0) {
12 table[i][j] = table[i][j-1]; // choose options

35
13 }
14 }
15 }
16
17 return table[x-1][y-1]; // return result
18 }

36
Top-Down vs. Bottom-Up
The top-down (recursive) solution is easy to develop, though it needs extra space for a recursive call
stack. The bottom-up (iterative) solution is not intuitive to come up with, but it avoids extra space.

From Top-Down to Bottom-Up

To derive an iterative solution from a recursive solution, we need to discover common patterns
between these two methods.

Step 1. Base Case

Reuse base cases.

Both methods have base cases to start and to finish operations. After finding a recursive solution, we
can use base cases of a recursive solution for an iterative solution.

1 int topDown(int n) {
2 if (base case) {
3 return result; // base case
4 }
5 }

1 int bottomUp(int n) {
2 table[base case] = result;
3 }

Fibonacci Sequence

1 int topDown(int n) {
2 if (n == 0) {
3 return 0; // base case
4 }
5 if (n == 1) {
6 return 1; // base case
7 }
8
9 ...
10 }

1 int bottomUp(int n) {
2 ...

37
3
4 table[0] = 0; // base case
5 table[1] = 1; // base case
6
7 ...
8 }

Coin Change

1 int topDown(int n) {
2 if (target == 0) {
3 return 0; // base case
4 }
5
6 ...
7 }

1 int bottomUp(int n) {
2 ...
3
4 table[0] = 0; // base case
5
6 ...
7 }

Unique Paths

1 int topDown(int n) {
2 if (x == 0 && y == 0) {
3 return 1; // base case
4 }
5 if (x < 0 || y < 0) {
6 return 0; // not valid sub-problem
7 }
8
9 ...
10 }

1 int bottomUp(int n) {
2 ...
3
4 table[0][0] = 1; // base case
5

38
 6 ...
7 }

Step 2. Table to Store Sub-State Solutions

Reuse the memoization table from a recursive solution.

In a recursive solution, there is a memoization table to store sub-state solutions. We can use the same
table for an iterative solution as well to store sub-state solutions.

Fibonacci Sequence

1 int topDown(int n, vector<int>& memo) {

2 ...
3
4 if (memo[n] != -1) {
5 return memo[n]; // check if the state was already calculated
6 }
7
8 memo[n] = /* result */
9
10 return result;
11 }

1 int bottomUp(int n) {
2 ...
3
4 for (...) {
5 table[n] = /* result */
6 }
7
8 return table[n];
9 }

Coin Change

1 int topDown(int target, vector<int> &coins, vector<int>& memo) {

2 ...
3
4 if (memo[target] != -1) {
5 return memo[target];
6 }
7

39
8 ...
9
10 memo[target] = /* result */
11
12 return result;
13 }

1 int bottomUp(int target, vector<int> &coins) {

2 ...
3
4 for (...) {
5 for (...) {
6 if (...) {
7 table[target] = /* result */
8 }
9 }
10 }
11
12 return table[target] == inf ? -1 : table[target];
13 }

Unique Paths

1 int topDown(int x, int y, vector<vector<int>>& memo) {

2 ...
3
4 if (memo[x][y] != -1) {
5 return memo[x][y];
6 }
7
8 memo[x][y] = /* result */
9
10 return result;
11 }

1 int bottomUp(int x, int y) {

2 int table[x][y];
3
4 ...
5
6 for (...) {
7 for (...) {
8 table[i][j] = /* result */
15 }

40
 16 }
17
18 return table[x-1][y-1];
19 }

Step 3. Iterative Function Calls

Write iterative function calls.

Now it’s time to find out how to replace recursive calls with iterative calls. Let’s recall the statement
from the paper.

“We have a physical system whose state at any time is determined by a set of quantities which we
call state parameters, or state variables (The Theory of Dynamic Programming, Richard Bellman).”

Consequently, we can use state parameters used in recursive calls for iterative calls as well.

Fibonacci Sequence

𝑛 is a state parameter transforming each state.

1 int topDown(int n, vector<int>& memo) {

2 ...
3
4 int result = Fib(n-1) + Fib(n-2); // n - transforming state parameter
5
6 memo[n] = result;
7
8 return result;
9 }

1 int bottomUp(int n) {
2 ...
3
4 for (int i = 2; i <= n; ++i) { // n - transforming state parameter
5 table[i] = /* result */
6 }
7
8 return table[n];
9 }

Coin Change

41
𝑡𝑎𝑟𝑔𝑒𝑡 is a state parameter transforming each state.

1 int topDown(int target, vector<int> &coins, vector<int>& memo) {

2 ...
3
4 for (...) {
5 if (coin <= target) {
6 result = CoinChange(target - coin, coins); // target - transforming
state parameter
7 }
8 }
9
10 memo[target] = result;
11
12 return result;
13 }

1 int bottomUp(int target, vector<int> &coins) {

2 ...
3
4 for (int i = 1; i <= target; ++i) { // target - transforming state parameter
5 for (...) {
6 if (...) {
7 table[i] = /* result */
8 }
9 }
10 }
11
12 return table[target] == inf ? -1 : table[target];
13 }

Unique Paths

𝑥 and 𝑦 are state parameters transforming each state.

1 int topDown(int x, int y, vector<vector<int>>& memo) {

2 ...
3
4 int result = UniquePaths(x-1, y) + UniquePaths(x, y-1); // x and y -
transforming state parameters
5
6 memo[x][y] = result;
7
8 return memo[x][y];

42
9 }

1 int bottomUp(int x, int y) {

2 ...
3
4 for (int i = 0; i < x; ++i) { // x - transforming state parameter
5 for (int j = 0; j < y; ++j) { // y - transforming state parameter
6 table[i][j] = /* result */
13 }
14 }
15
16 return table[x-1][y-1];
17 }

Step 4. Iterate Over Options

Both top-down and bottom-up approaches require iterating over all possible options to find the
most optimal solution to reach a target state.

Fibonacci Sequence

𝑡𝑎𝑏𝑙𝑒(𝑛 − 1)
𝑡𝑎𝑏𝑙𝑒(𝑛) →
𝑡𝑎𝑏𝑙𝑒(𝑛 − 2)

𝑡𝑎𝑏𝑙𝑒 refers to a table to store solutions for sub-problems.

To obtain 𝑛!" term, there are two options to come from to the current state:
• the last term
• one before the last term

1 int topDown(int n, vector<int>& memo) {

2 ...
3
4 int result = Fib(n-1) + Fib(n-2); // Iterate over all options.
5
6 memo[n] = result;
7
8 return result;
9 }

1 int bottomUp(int n) {
2 ...

43
3
4 for (int i = 2; i <= n; ++i) {
5 table[i] = table[i-1] + table[i-2];. // Iterate over all options
6 }
7
8 return table[n];
9 }

Coin Change

𝑡𝑎𝑏𝑙𝑒(𝑡𝑎𝑟𝑔𝑒𝑡 − 𝑐𝑜𝑖𝑛 𝑤𝑖𝑡ℎ 𝑑𝑒𝑛𝑜𝑚𝑖𝑛𝑎𝑡𝑖𝑜𝑛 5)

𝑡𝑎𝑏𝑙𝑒(𝑡𝑎𝑟𝑔𝑒𝑡) → 𝑡𝑎𝑏𝑙𝑒(𝑡𝑎𝑟𝑔𝑒𝑡 − 𝑐𝑜𝑖𝑛 𝑤𝑖𝑡ℎ 𝑑𝑒𝑛𝑜𝑚𝑖𝑛𝑎𝑡𝑖𝑜𝑛 3)
𝑡𝑎𝑏𝑙𝑒(𝑡𝑎𝑟𝑔𝑒𝑡 − 𝑐𝑜𝑖𝑛 𝑤𝑖𝑡ℎ 𝑑𝑒𝑛𝑜𝑚𝑖𝑛𝑎𝑡𝑖𝑜𝑛 1)

To make the target amount, there are three options to come from to the current state:
• using the coin with denomination 5
• using the coin with denomination 3
• using the coin with denomination 1

1 int topDown(int target, vector<int>& coins, vector<int>& memo) {

2 ...
3
4 for (int i = 0; i < coins.size(); ++i) { // Iterate over all options.
5 if (coins[i] <= target) {
6 result = min(result, CoinChange(target - coins[i], coins) + 1);
7 }
8 }
9
10 memo[target] = result;
11
12 return result;
13 }

1 int bottomUp(int target, vector<int> &coins) {

2 ...
3
4 for (int i = 1; i <= target; ++i) {
5 for (int j = 0; j < coins.size(); ++j) { // Iterate over all options.
6 if (coins[j] <= i) {
7 table[i] = min(table[i], table[i - coins[j]] + 1);
8 }
9 }
10 }

44
11
12 return table[target] == inf ? -1 : table[target];
13 }

Unique Paths

𝑡𝑎𝑏𝑙𝑒(𝑥 − 1, 𝑦)
𝑡𝑎𝑏𝑙𝑒(𝑥, 𝑦) →
𝑡𝑎𝑏𝑙𝑒(𝑥, 𝑦 − 1)

To reach the target, there are two options (directions) to come from to the current state:
• from top 𝑥 − 1
• from left 𝑦 − 1

1 int topDown(int x, int y, vector<vector<int>>& memo) {

2 ...
3
4 memo[x][y] = UniquePaths(x-1, y) + UniquePaths(x, y-1); // Iterate over all
options and reduce the problem with the current option.
5
6 return memo[x][y];
7 }

1 int bottomUp(int x, int y) {

2 ...
3
4 for (int i = 0; i < x; ++i) { // x - transforming state parameter
5 for (int j = 0; j < y; ++j) { // y - transforming state parameter
6 if (i > 0 && j > 0) {
7 table[i][j] = table[i-1][j] + table[i][j-1]; // Iterate over all
options.
8 } else if (i > 0) {
9 table[i][j] = table[i-1][j]; // Iterate over all options.
10 } else if (j > 0) {
11 table[i][j] = table[i][j-1]; // Iterate over all options.
12 }
13 }
14 }
15
16 return table[x-1][y-1];
17 }

45
 Step 5. Choose an Optimal Solution
Find an optimal solution (maximum, minimum, shortest, longest, etc.) among all states and add a
value for the current state.

For every state, we need to choose the most optimal sub-state solution and add the value for the
current state.

Fibonacci Sequence

𝑡𝑎𝑏𝑙𝑒(𝑛) = 𝑡𝑎𝑏𝑙𝑒(𝑛 − 1) + 𝑡𝑎𝑏𝑙𝑒(𝑛 − 2)

Sum up two previous values.

1 int topDown(int n, vector<int>& memo) {

2 ...
3
4 int result = Fib(n-1) + Fib(n-2); // Sum up two previous values
5
6 memo[n] = result;
7
8 return result;
9 }

1 int bottomUp(int n) {
2 ...
3
4 for (int i = 2; i <= n; ++i) {
5 table[i] = table[i-1] + table[i-2];. // Sum up two previous values
6 }
7
8 return table[n];
9 }

Coin Change

𝑡𝑎𝑏𝑙𝑒 (𝑡𝑎𝑟𝑔𝑒𝑡 − 𝑐𝑜𝑖𝑛 𝑤𝑖𝑡ℎ 𝑑𝑒𝑛𝑜𝑚𝑖𝑛𝑎𝑡𝑖𝑜𝑛 5)

𝑡𝑎𝑏𝑙𝑒(𝑡𝑎𝑟𝑔𝑒𝑡) = 𝑚𝑖𝑛 < 𝑡𝑎𝑏𝑙𝑒(𝑡𝑎𝑟𝑔𝑒𝑡 − 𝑐𝑜𝑖𝑛 𝑤𝑖𝑡ℎ 𝑑𝑒𝑛𝑜𝑚𝑖𝑛𝑎𝑡𝑖𝑜𝑛 3) ? + 1
𝑡𝑎𝑏𝑙𝑒(𝑡𝑎𝑟𝑔𝑒𝑡 − 𝑐𝑜𝑖𝑛 𝑤𝑖𝑡ℎ 𝑑𝑒𝑛𝑜𝑚𝑖𝑛𝑎𝑡𝑖𝑜𝑛 1)

Find an optimal solution without the current state and add one coin for the current state.

1 int topDown(int target, vector<int>& coins, vector<int>& memo) {

2 ...

46
3
4 for (int i = 0; i < coins.size(); ++i) { // Iterate over all options.
5 if (coins[i] <= target) {
6 result = min(result, CoinChange(target - coins[i], coins) + 1); // Find
an optimal solution
7 }
8 }
9
10 memo[target] = result;
11
12 return result;
13 }

1 int bottomUp(int target, vector<int> &coins) {

2 ...
3
4 for (int i = 1; i <= target; ++i) {
5 for (int j = 0; j < coins.size(); ++j) { // Iterate over all options.
6 if (coins[j] <= i) {
7 table[i] = min(table[i], table[i - coins[j]] + 1); // Find an
optimal solution
8 }
9 }
10 }
11
12 return table[target] == inf ? -1 : table[target];
13 }

Unique Paths

𝑡𝑎𝑏𝑙𝑒(𝑥, 𝑦) = 𝑡𝑎𝑏𝑙𝑒(𝑥 − 1, 𝑦) + 𝑡𝑎𝑏𝑙𝑒(𝑥, 𝑦 − 1)

Sum up both options to find the total number of paths.

1 int topDown(int x, int y, vector<vector<int>>& memo) {

2 ...
3
4 memo[x][y] = UniquePaths(x-1, y) + UniquePaths(x, y-1); // Sum up both options
to find a total path.
5
6 return memo[x][y];
7 }

1 int bottomUp(int x, int y) {

47
2 ...
3
4 for (int i = 0; i < x; ++i) { // x - transforming state parameter
5 for (int j = 0; j < y; ++j) { // y - transforming state parameter
6 if (i > 0 && j > 0) {
7 table[i][j] = table[i-1][j] + table[i][j-1]; // Sum up both options
to find a total path.
8 } else if (i > 0) {
9 table[i][j] = table[i-1][j]; // Sum up both options to find a total
path.
10 } else if (j > 0) {
11 table[i][j] = table[i][j-1]; // Sum up both options to find a total
path.
12 }
13 }
14 }
15
16 return table[x-1][y-1];
17 }

Step 6. Return Result

After reaching a target state, return an answer for the target state.

Fibonacci Sequence

return table[n]

Coin Change

return table[target]

Unique Paths

return table[x-1][y-1]

48
Practicing Common Dynamic Programming Problems

Minimum Cost Climbing Stairs

Find the minimum cost required to reach the top stair from the bottom stair, climbing either 1 or 2
stairs each time. To climb, you need to pay the cost.

Intuition
For every stair, we choose an option that leads to the minimum cost among all possible options
before the current stair, and we add the cost for the current stair.

Top-Down

Step 1. Iterate Over Options

When we solve a problem recursively, for every sub-problem (state), we have different options
(directions) to choose to reach our target. We need to iterate over all possible options to find the
most optimal solution.

To reach the top stair, there are two options to choose from:
• climb 1 stair
• climb 2 stairs
𝐹(𝑐𝑙𝑖𝑚𝑏 1 𝑠𝑡𝑎𝑖𝑟)
𝐹(𝑐𝑢𝑟𝑟𝑒𝑛𝑡 𝑠𝑡𝑎𝑖𝑟) →
𝐹(𝑐𝑙𝑖𝑚𝑏 2 𝑠𝑡𝑎𝑖𝑟𝑠)

Step 2. Reduce Target

Choosing every option, we reduce a target to a particular value, and we call a recursive function
again with the new updated target.

𝐹(𝑛 − 1)
𝐹(𝑛) →
𝐹(𝑛 − 2)

• Climbing 1 stair reduces the problem to find the minimum cost required to reach 𝑛 − 1!" stair.
• Climbing 2 stairs reduces the problem to find the minimum cost required to reach 𝑛 − 2!" stair.

𝑚𝑖𝑛𝐶𝑜𝑠𝑡(𝑛 − 1, 𝑐𝑜𝑠𝑡, 𝑚𝑒𝑚𝑜)

𝑟𝑒𝑠𝑢𝑙𝑡 →
𝑚𝑖𝑛𝐶𝑜𝑠𝑡(𝑛 − 2, 𝑐𝑜𝑠𝑡, 𝑚𝑒𝑚𝑜)

49
 Step 3. Choose Optimal Solution
After coming from recursive calls, we choose an optimal solution among these calls and add the
value for the current state.

𝐹(𝑛 − 1)
𝐹(𝑛) = 𝑚𝑖𝑛 ` a + 𝑐𝑜𝑠𝑡
𝐹(𝑛 − 2)

We choose the minimum cost among all sub-problem solutions before the current stair, and we add
the cost for the current stair.

𝑚𝑖𝑛𝐶𝑜𝑠𝑡(𝑛 − 1, 𝑐𝑜𝑠𝑡, 𝑚𝑒𝑚𝑜)

𝑟𝑒𝑠𝑢𝑙𝑡 = 𝑚𝑖𝑛 ` a + 𝑐𝑜𝑠𝑡[𝑛]
𝑚𝑖𝑛𝐶𝑜𝑠𝑡(𝑛 − 2, 𝑐𝑜𝑠𝑡, 𝑚𝑒𝑚𝑜)

Step 4. Base Case

When we reach a base case, we need to quit a recursive function. The base case can be a base state
or case when a sub-problem is no longer valid (in this case, when it returns the worst result).

If you start to climb from 0 floor, you will pay 𝑐𝑜𝑠𝑡[0], and if you start to climb from 1st floor, you will
pay 𝑐𝑜𝑠𝑡[1].

if (n == 0) {
return cost[0]; // base case
}
if (n == 1) {
return cost[1]; // base case
}

Step 5. Memoization
We use transforming state variables for memorization.

𝑛 is a state variable transforming each state. We can use it for memoization.

if (memo[n] != -1) {
return memo[n];
}

Step 6. Return Result

Return a result of a recursive function.

50
return result

Solution

1 int topDown(int n, vector<int>& cost, vector<int>& memo) {

2 if (n == 0) {
3 return cost[n]; // base case
4 }
5 if (n == 1) {
6 return cost[n]; // base case
7 }
8
9 if (memo[n] != -1) {
10 return memo[n];
11 }
12
13 int result = min(minCost(n-1, cost, memo), minCost(n-2, cost, memo)) + (n ==
cost.size() ? 0 : cost[n]);
14
15 return memo[n] = result;
16 }

Analysis

Time-Complexity: 𝑂(𝑛)

We are calling the function two times and have a total of 𝑛 states, where 𝑛 is the number of stairs.

Space-Complexity: 𝑂(𝑛)

We are using 𝑛 space to store sub-state solutions.

Bottom-Up

Step 1. Base Case

Find a base case for a given problem.

Base cases are 𝑛 = 0 and 𝑛 = 1 because we can start climbing from stairs 0 and 1 and know the costs
for these stairs.

dp[0] = cost[0]; // base case

dp[1] = cost[1]; // base case

51
 Step 2. Move Toward a Target State
Starting from a base case, we move toward a target state.

We already know the solution for the base cases. To find solutions for other stairs, we iterate till 𝑛.

dp[0] = cost[0]; // base case

dp[1] = cost[1]; // base case

for (int i = 2; i <= n; ++i) { // move towards n

/* code */
}

Step 3. Iterate Over Options

For every step (state), we have several options (ways) to choose to come to the current state. We
need to iterate all possible options to find the most optimal solution for the current state.

We can come to the current stair either by climbing 1 or 2 stairs.

for (int i = 2; i <= n; ++i) {

dp[i] <- dp[i-1], dp[i-2]; // iterate over options
}

Step 4. Choose an Optimal Solution

We find an optimal solution (maximum, minimum, shortest, longest, etc.) without the current state
and add a value for the current state.

We choose an option with the minimum cost before the current stair, and we add the cost for the
current stair.

for (int i = 2; i <= n; ++i) {

dp[i] = min(dp[i-1], dp[i-2]) + cost[i];
}

Step 5. Return Result

After reaching a target state, return an answer for the target state.

We return the answer for the target stair.

return dp[n]

52
Solution

1 int bottomUp(vector<int>& cost) {

2 int n = (int)cost.size();
3
4 vector<int> dp(n+1);
5
6 dp[0] = cost[0]; // base case
7 dp[1] = cost[1]; // base case
8
9 for (int i = 2; i <= n; ++i) {
10 dp[i] = min(dp[i-1], dp[i-2]) + (i == n ? 0 : cost[i]);
11 }
12
13 return dp[n];
14 }

Analysis

Time-Complexity: 𝑂(𝑛)

Inside the single loop, we are performing constant 𝑂(1) operations 𝑛 times, where 𝑛 is the number of
stairs.

Space-Complexity: 𝑂(𝑛)

We are using 𝑛 space to store sub-state solutions.

53
Minimum Path Sum

Given a 2D grid with non-negative numbers, find the path from the top-left corner to the bottom-
right corner with the minimum sum of all numbers along the path.

Intuition
For every position, we choose the path with the minimum sum among all paths before the
current position, and we add the value for the current position.

Top-Down

Step 1. Iterate Over Options

When we solve a problem recursively, for every sub-problem (state), we have different options
(directions) to choose to reach our target. We need to iterate over all possible options to find the
most optimal solution.

To reach the target position, there are two options to choose from:
• move down 𝑖 + 1
• move right 𝑗 + 1

𝐹(𝑚𝑜𝑣𝑒 𝑑𝑜𝑤𝑛)
𝐹(𝑡𝑎𝑟𝑔𝑒𝑡 𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛) →
𝐹(𝑚𝑜𝑣𝑒 𝑟𝑖𝑔ℎ𝑡)

Step 2. Reduce Target

Choosing every option, we reduce a target to a particular value, and we call a recursive function
again with the new updated target.

𝐹(𝑖 + 1, 𝑗)
𝐹(𝑡𝑎𝑟𝑔𝑒𝑡 𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛) →
𝐹(𝑖, 𝑗 + 1)

• Moving down 𝑖 + 1 makes us closer to the target position in terms of a row.

• Moving right 𝑗 + 1 makes us closer to the target position in terms of a column.

𝑝𝑎𝑡ℎ𝑆𝑢𝑚(𝑖 + 1, 𝑗, 𝑔𝑟𝑖𝑑, 𝑚𝑒𝑚𝑜)

𝑟𝑒𝑠𝑢𝑙𝑡 →
𝑝𝑎𝑡ℎ𝑆𝑢𝑚(𝑖, 𝑗 + 1, 𝑔𝑟𝑖𝑑, 𝑚𝑒𝑚𝑜)

54
 Step 3. Choose Optimal Solution
After coming from recursive calls, we choose an optimal solution among these calls and add the
value for the current state.

𝐹(𝑖 + 1, 𝑗)
𝐹(𝑛) = 𝑚𝑖𝑛 ` a + 𝑣𝑎𝑙𝑢𝑒
𝐹(𝑖, 𝑗 + 1)

We choose the minimum sum among sub-problem solutions, and we add the value for the current
position.

𝑝𝑎𝑡ℎ𝑆𝑢𝑚(𝑖 + 1, 𝑗, 𝑔𝑟𝑖𝑑, 𝑚𝑒𝑚𝑜)

𝑟𝑒𝑠𝑢𝑙𝑡 = 𝑚𝑖𝑛 ` a + 𝑔𝑟𝑖𝑑[𝑖 ][𝑗]
𝑝𝑎𝑡ℎ𝑆𝑢𝑚(𝑖, 𝑗 + 1, 𝑔𝑟𝑖𝑑, 𝑚𝑒𝑚𝑜)

Step 4. Base Case

When we reach a base case, we need to quit a recursive function. The base case can be a base state
or case when a sub-problem is no longer valid (in this case, when it returns the worst result).

If the position reaches the target position, there is no need to move further; we return the value for the
target position. If the position is out of bounds of the grid, then the problem becomes invalid, we
return the worst result.

// reach the target

if (i == grid.size()-1 && j == grid[0].size()-1) {
return grid[i][j];
}

// invalid position
if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size()) {
return INT_MAX;
}

Step 5. Memoization
We use transforming state variables for memorization.

Indices 𝑖 and 𝑗 are state variables transforming each state. We can use them for memoization.

if (memo[i][j] != -1) {
return memo[i][j];
}

55
 Step 6. Return Result
Return a result of a recursive function.

return memo[i][j]

Solution

int pathSum(int i, int j, vector<vector<int>>& grid, vector<vector<int>>& memo) {

// reach the target
if (i == grid.size()-1 && j == grid[0].size()-1) {
return grid[i][j];
}

// invalid position
if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size()) {
return INT_MAX;
}

if (memo[i][j] != -1) {
return memo[i][j];
}

int result = min(pathSum(i+1, j, grid, memo), pathSum(i, j+1, grid, memo)) +

grid[i][j];

memo[i][j] = result;
return result;
}

Analysis

Time-Complexity: 𝑂(𝑛𝑚)

We are calling the function two times and have a total of 𝑛𝑚 states, where 𝑛 is the number of rows and
𝑚 is the number of columns.

Space-Complexity: 𝑂(𝑛𝑚)

We are using 𝑛𝑚 space to store sub-state solutions.

56
Bottom-Up

Step 1. Base Case

Find a base case for a given problem.

For base cases, we can calculate the values for the first row ignoring other rows. This means that we
have only one option to choose from, the same row previous column. Similarly, we can calculate the
values for the first column ignoring other columns. In this case, we can choose only the same column
previous row.

for (int j = 1; j < m; ++j) {

grid[0][j] += grid[0][j-1];
}

for (int i = 1; i < n; ++i) {

grid[i][0] += grid[i-1][0];
}

Step 2. Move Toward a Target State

Starting from a base case, we move toward a target state.

We iterate over all positions moving towards the target position (𝑛 − 1, 𝑚 − 1).

for (int i = 1; i < n; ++i) {

for (int j = 1; j < m; ++j) {
/* code */
}
}

Step 3. Iterate Over Options

For every step (state), we have several options (ways) to choose to come to the current state. We
need to iterate all possible options to find the most optimal solution for the current state.

We can come to the current position from the top (𝑖 − 1, 𝑗) and the left (𝑖, 𝑗 − 1) side positions.

for (int i = 1; i < n; ++i) {

for (int j = 1; j < m; ++j) {
grid[i][j] <- grid[i-1][j], grid[i][j-1]
}

57
}

Step 4. Choose an Optimal Solution

We find an optimal solution (maximum, minimum, shortest, longest, etc.) without the current state
and add a value for the current state.

We choose an option with the minimum sum and add the value for the current position.

for (int i = 1; i < n; ++i) {

for (int j = 1; j < m; ++j) {
grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j];
}
}

Step 5. Return Result

After reaching a target state, return an answer for the target state.

We return the answer for the target position.

return grid[n-1][m-1]

Solution

int minPathSum(vector<vector<int>>& grid) {

if (grid.size() == 0) {
return 0;
}

int n = (int)grid.size();
int m = (int)grid[0].size();

for (int j = 1; j < m; ++j) {

grid[0][j] += grid[0][j-1];
}

for (int i = 1; i < n; ++i) {

grid[i][0] += grid[i-1][0];
}

for (int i = 1; i < n; ++i) {

for (int j = 1; j < m; ++j) {

58
 grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j];
}
}

return grid[n-1][m-1];
}

Analysis

Time-Complexity: 𝑂(𝑛𝑚)

Inside the nested loop, we are performing constant 𝑂(1) operations 𝑛𝑚 times, where 𝑛 is the number
of rows and 𝑚 is the number of columns.

Space-Complexity: 𝑂(𝑛𝑚)

We are using 𝑛𝑚 space to store sub-state solutions.

59
Climbing Stairs

Find the number of distinct ways to reach the top stair from the bottom stair, climbing either 1 or 2
stairs each time.

Intuition
For every stair, we sum all possible ways to reach the current stair. The solution for the top stair
will be the answer.

Top-Down

Step 1. Iterate Over Options

When we solve a problem recursively, for every sub-problem (state), we have different options
(directions) to choose to reach our target. We need to iterate over all possible options to find the
most optimal solution.

To reach the top stair, there are two options to choose from:
• climb 1 stair
• climb 2 stairs

𝐹(𝑐𝑙𝑖𝑚𝑏 1 𝑠𝑡𝑎𝑖𝑟)
𝐹(𝑐𝑢𝑟𝑟𝑒𝑛𝑡 𝑠𝑡𝑎𝑖𝑟) →
𝐹(𝑐𝑙𝑖𝑚𝑏 2 𝑠𝑡𝑎𝑖𝑟𝑠)

Step 2. Reduce Target

Choosing every option, we reduce a target to a particular value, and we call a recursive function
again with the new updated target.

𝐹(𝑛 − 1)
𝐹(𝑛) →
𝐹(𝑛 − 2)

• Climbing 1 stair reduces the problem to find the number of distinct ways to reach the 𝑛 − 1!"
stair.
• Climbing 2 stairs reduces the problem to find the number of distinct ways to reach the 𝑛 − 2!"
stair.

𝑐𝑙𝑖𝑚𝑏𝑆𝑡𝑎𝑖𝑟𝑠(𝑛 − 1, 𝑐𝑜𝑠𝑡, 𝑚𝑒𝑚𝑜)

𝑟𝑒𝑠𝑢𝑙𝑡 →
𝑐𝑙𝑖𝑚𝑏𝑆𝑡𝑎𝑖𝑟𝑠(𝑛 − 2, 𝑐𝑜𝑠𝑡, 𝑚𝑒𝑚𝑜)

60
 Step 3. Choose Optimal Solution
After coming from recursive calls, we choose an optimal solution among these calls and add the
value for the current state.

We sum up both options to get a total number of distinct ways.

𝐹(𝑛) = 𝐹(𝑛 − 1) + 𝐹(𝑛 − 2)

𝑟𝑒𝑠𝑢𝑙𝑡 = 𝑐𝑙𝑖𝑚𝑏𝑆𝑡𝑎𝑖𝑟𝑠(𝑛 − 1, 𝑚𝑒𝑚𝑜) + 𝑐𝑙𝑖𝑚𝑏𝑆𝑡𝑎𝑖𝑟𝑠(𝑛 − 2, 𝑚𝑒𝑚𝑜)

Step 4. Base Case

When we reach a base case, we need to quit a recursive function. The base case can be a base state
or case when a sub-problem is no longer valid (in this case, when it returns the worst result).

The following scenarios can be base cases:

• If there is 0 floor left to climb, there is only one distinct way.
• If there is 1 floor left to climb, there is only one distinct way to reach the top, to climb 1 stair.

if (n < 2) {
return 1; // base case
}

Step 5. Memoization
We use transforming state variables for memorization.

𝑛 is a state variable transforming each state. We will use it for memoization.

if (memo[n] != -1) {
return memo[n];
}

Step 6. Return Result

Return a result of a recursive function.

return memo[n]

Solution

int climbStairs(int n, vector<int>& memo) {

61
 if (n < 2) {
return 1; // base case
}

if (memo[n] != -1) {
return memo[n];
}

memo[n] = climbStairs(n-1, memo) + climbStairs(n-2, memo);

return memo[n];
}

Analysis

Time-Complexity: 𝑂(𝑛)

We are calling the function two times and have a total of 𝑛 states, where 𝑛 is the number of stairs.

Space-Complexity: 𝑂(𝑛)

We are using 𝑛 space to store sub-state solutions.

Bottom-Up

Step 1. Base Case

Find a base case for a given problem.

The following scenarios can be base cases:

• If there is 0 floor left to climb, there is only one distinct way.
• If there is 1 floor left to climb, there is only one distinct way to reach the top, to climb 1 stair.

dp[0] = 1; // base case

dp[1] = 1; // base case

Step 2. Move Toward a Target State

Starting from a base case, we move toward a target state.

We already know the answer for the base cases. We iterate over other floors till 𝑛!" floor to find out
solutions for the rest of the floors.

62
dp[0] = 1; // base case
dp[1] = 1; // base case

for(int i = 2; i<=n; i++) { // move towards n

/* code */
}

Step 3. Iterate Over Options

For every step (state), we have several options (ways) to choose to come to the current state. We
need to iterate all possible options to find the most optimal solution for the current state.

We can come to the current stair either by making 1 or 2 climbs.

for (int i = 2; i<=n; ++i) {

dp[i] = ...; // iterate over options
}

Step 4. Choose an Optimal Solution

We find an optimal solution (maximum, minimum, shortest, longest, etc.) without the current state
and add a value for the current state.

We sum up all possible options.

For (int i = 2; i<=n; ++i) {

dp[i] = dp[i-1] + dp[i-2];
}

Step 5. Return Result

After reaching a target state, return an answer for the target state.

We return the answer for the top stair.

Return dp[n]

Solution

int bottomUp(int n) {
if(n < 2) {

63
 return 1; // early exit
}

int dp[n+1];

dp[0] = 1; // base case

dp[1] = 1; // base case

for(int i = 2; i<=n; i++) {

dp[i] = dp[i-1] + dp[i-2];
}

return dp[n];
}

Analysis

Time-Complexity: 𝑂(𝑛)

Inside the single loop, we are performing constant 𝑂(1) operations 𝑛 times.

Space-Complexity: 𝑂(𝑛)

We are using 𝑛 space to store sub-state solutions.

Note

Some questions point out the number of repetitions. In that case, add one more loop to simulate
every repetition.

64
Burst Balloons

Given balloons with values, after the burst of 𝑖!" balloon you will get 𝑏𝑎𝑙𝑙𝑜𝑜𝑛𝑠[𝑖 − 1] ∗ 𝑏𝑎𝑙𝑙𝑜𝑜𝑛𝑠[𝑖] ∗
𝑏𝑎𝑙𝑙𝑜𝑜𝑛𝑠[𝑖 + 1] coins. After each burst, balloons 𝑖 − 1 and 𝑖 + 1 become adjacent. Find the maximum
number of coins you can get by bursting balloons.

Intuition

We iterate over every interval, then for every balloon in the interval, we check the possible
maximum number of coins we can get if we burst this balloon last.

Top-Down

Step 1. Iterate Over Options

When we solve a problem recursively, for every sub-problem (state), we have different options
(directions) to choose to reach our target. We need to iterate over all possible options to find the
most optimal solution.

We have several options to burst balloons. For every interval in the list of balloons, we can try to burst
balloons at every index last to get the maximum number of coins. Therefore, we need to iterate
through indices of balloons.

// starting from i to j
for (int k = i; k <= j; ++k) {
/* code */
}

Step 2. Reduce Target

Choosing every option, we reduce a target to a particular value, and we call a recursive function
again with the new updated target.

Every time we choose some index to burst a balloon, we split the array of balloons into two parts at
that index (excluding the index). Then we call the recursive function again with the new intervals.

𝐹(𝑖, 𝑘 − 1)
𝐹(𝑛) → 𝑝𝑟𝑜𝑑𝑢𝑐𝑡(𝑘)
𝐹(𝑘 + 1, 𝑗)
Choosing index 𝑘:
• The first half will be from 𝑖 till 𝑘 − 1.
• The second half will be from 𝑘 + 1 till 𝑗.

65
 𝑡𝑜𝑝𝐷𝑜𝑤𝑛(𝑛𝑢𝑚𝑠, 𝑖, 𝑘 − 1, 𝑚𝑒𝑚𝑜)
𝑟𝑒𝑠𝑢𝑙𝑡 → 𝑛𝑢𝑚𝑠[𝑖 − 1] ∗ 𝑛𝑢𝑚𝑠[𝑘] ∗ 𝑛𝑢𝑚𝑠[𝑗 + 1]
𝑡𝑜𝑝𝐷𝑜𝑤𝑛(𝑛𝑢𝑚𝑠, 𝑘 + 1, 𝑗, 𝑚𝑒𝑚𝑜)

Step 3. Choose Optimal Solution

After coming from recursive calls, we choose an optimal solution among these calls and add the
value for the current state.

𝐹(𝑛) = 𝐹(𝑖, 𝑘 − 1) + 𝑝𝑟𝑜𝑑𝑢𝑐𝑡(𝑘) + 𝐹(𝑘 + 1, 𝑗)

For every interval, if we decide to burst the balloon in the interval last, we get the best from the left and
right sides. Then we add the product of the current balloon with two neighbouring balloons outside
the interval. The reason for that is the fact that when we burst the current balloon last, we do not have
other unburst balloons in the interval. Remember that each time we burst a balloon, two neighbouring
balloons become adjacent.

𝑟𝑒𝑠𝑢𝑙𝑡 = 𝑡𝑜𝑝𝐷𝑜𝑤𝑛(𝑛𝑢𝑚𝑠, 𝑖, 𝑘 − 1, 𝑚𝑒𝑚𝑜) + 𝑛𝑢𝑚𝑠[𝑖 − 1] ∗ 𝑛𝑢𝑚𝑠[𝑘] ∗ 𝑛𝑢𝑚𝑠[𝑗 + 1] +

𝑡𝑜𝑝𝐷𝑜𝑤𝑛(𝑛𝑢𝑚𝑠, 𝑘 + 1, 𝑗, 𝑚𝑒𝑚𝑜)

Step 4. Base Case

When we reach a base case, we need to quit a recursive function. The base case can be a base state
or case when a sub-problem is no longer valid (in this case, when it returns the worst result).

The following scenarios can be base cases:

• If we can’t further divide the interval into two halves 𝑖 == 𝑗.
• If the interval is not valid, 𝑖 < 𝑗.

if (i > j) {
return 0; // base case
}

if (i == j) {
return nums[i]; // base case
}

Step 5. Memoization
We use transforming state variables for memorization.

66
Starting index 𝑖 and ending index 𝑗 are state variables transforming each state. We can use them for
memorization.

if (memo[i][j] != -1) {
return memo[i][j];
}

Step 6. Return Result

Return a result of a recursive function.

return result

Solution

int topDown(vector<int>& nums, int i, int j, vector<vector<int>>& memo) {

if (i > j) {
return 0; // base case
}

if (i == j) {
return (i-1 >= 0 ? nums[i-1] : 1) * nums[i] * (j+1 < nums.size() ? nums[j+1] :
1);
}

if (memo[i][j] != -1) {
return memo[i][j];
}

int result = INT_MIN;

for (int k = i; k <= j; ++k) {

result = max(result, topDown(nums, i, k-1, memo) + (i-1 >= 0 ? nums[i-1] : 1) *
nums[k] * (j+1 < nums.size() ? nums[j+1] : 1) + topDown(nums, k+1, j, memo));
}

memo[i][j] = result

return result;
}

67
Analysis

Time-Complexity: 𝑂(𝑛0 )

We are calling the function 𝑛 times and have a total of 𝑛1 states, where 𝑛 is the number of balloons.

Space-Complexity: 𝑂(𝑛1 )

We are using 𝑛1 space to store sub-state solutions.

Bottom-Up

Step 1. Base Case

Find a base case for a given problem.

We can calculate a base case for an interval with a length less than or equal to three.

𝑛𝑢𝑚𝑠[0], 𝑛𝑢𝑚𝑠[1], 𝑛𝑢𝑚𝑠[2]

𝑛𝑢𝑚𝑠[1], 𝑛𝑢𝑚𝑠[2], 𝑛𝑢𝑚𝑠[3]

𝑛𝑢𝑚𝑠[𝑛 − 2], 𝑛𝑢𝑚𝑠[𝑛 − 1], 𝑛𝑢𝑚𝑠[𝑛]

int dp[n+1][n+1];

memset(dp, 0, sizeof dp);

for(int i = 0; i < n; i++) {

dp[i][i] = (i > 0 ? nums[i-1] : 1) * nums[i] * (i < n-1 ? nums[i+1] : 1);
}

Step 2. Move Toward a Target State

Starting from a base case, we move toward a target state.

We need to find an answer for the whole interval; therefore, we will be increasing the interval by
increasing the length of the interval (considering one more element each time).

for(int l = 1; l < n; l++) {

for(int i = 0; i < n-l; i++) {
int j = i+l;
// interval from i to j
}

68
 }

Step 3. Iterate Over Options

For every step (state), we have several options (ways) to choose to come to the current state. We
need to iterate all possible options to find the most optimal solution for the current state.

For every interval, we have several options to burst balloons. We can try to burst balloons at every
index to get the maximum number of coins. Therefore, we need to iterate through indices of balloons
𝑘.

for(int l = 1; l < n; l++) {

for(int i = 0; i < n-l; i++) {
int j = i+l;
// interval from i to j
for(int k = i; k <= j; k++) {
// try every index
}
}
}

Step 4. Choose an Optimal Solution

We find an optimal solution (maximum, minimum, shortest, longest, etc.) without the current state
and add a value for the current state.

For every interval, we iterate over balloons in the interval. Then we check the maximum number of
coins we can get if we burst the current balloon last. If we burst the current balloon last, we take
maximum values from the left and right sides and add a product of the current balloon with left and
right balloons outside the interval.

for(int l = 1; l < n; l++) {

for(int i = 0; i < n-l; i++) {
int j = i+l;
for(int k = i; k <= j; k++) {
dp[i][j] = max(dp[i][j], dp[i][k-1] + nums[i-1] * nums[k] * nums[j+1] +
dp[k+1][j]);
}
}
}

69
 Step 5. Return Result
After reaching a target state, return an answer for the target state.

We return the answer for the target state.

return dp[0][n-1]

Solution

int bottomUp(vector<int>& nums) {

if(nums.size() == 0) {
return 0;
}

int n = (int)nums.size();

int dp[n+1][n+1];

memset(dp, 0, sizeof dp);

for(int i = 0; i < n; i++) {

dp[i][i] = (i>0 ? nums[i-1] : 1) * nums[i] * (i<n-1 ? nums[i+1] : 1);
}

for(int l = 1; l < n; l++) {

for(int i = 0; i < n-l; i++) {
int j = i+l;
for(int k = i; k <= j; k++) {
int leftVal = (k>i && k>0) ? dp[i][k-1] : 0;
int rightVal = (k<j && k<n-1) ? dp[k+1][j] : 0;
int product = (i>0 ? nums[i-1] : 1)*nums[k]*(j<n-1 ? nums[j+1] : 1);
dp[i][j] = max(dp[i][j], leftVal + product + rightVal);
}
}
}

return dp[0][n-1];
}

70
Analysis

Time-Complexity: 𝑂(𝑛0 )

Inside the nested loop, we are performing constant operations 𝑛0 times, where 𝑛 is the number of
balloons.

Space-Complexity: 𝑂(𝑛1 )

We are using 𝑛1 space to store sub-state solutions.

71
Longest Common Subsequence

Given two strings, 𝑠𝑡𝑟𝑖𝑛𝑔 1 and 𝑠𝑡𝑟𝑖𝑛𝑔 2, find the length of the longest common subsequence in
these strings.

𝑖 − 𝑡ℎ𝑒 𝑖𝑛𝑑𝑒𝑥 𝑜𝑓 𝑠𝑡𝑟𝑖𝑛𝑔 1

𝑗 − 𝑡ℎ𝑒 𝑖𝑛𝑑𝑒𝑥 𝑜𝑓 𝑠𝑡𝑟𝑖𝑛𝑔 2

Top-Down

Step 1. Iterate Over Options

When we solve a problem recursively, for every sub-problem (state), we have different options
(directions) to choose to reach our target. We need to iterate over all possible options to find the
most optimal solution.

For each state, there are three options to choose from:

• If characters at indices 𝑖 and 𝑗 match, move indices for both strings.
• Move the index 𝑖 for 𝑠𝑡𝑟𝑖𝑛𝑔 1.
• Move the index 𝑗 for 𝑠𝑡𝑟𝑖𝑛𝑔 2.

Step 2. Reduce Target

Choosing every option, we reduce a target to a particular value, and we call a recursive function
again with the new updated target.

𝐹(𝑖 + 1, 𝑗)
𝐹(𝑖, 𝑗) → 𝐹(𝑖 + 1, 𝑗 + 1)
𝐹(𝑖, 𝑗 + 1)

For each state, we choose one of the three options and call the recursive function again with updated
indices:
• If characters at indices 𝑖 and 𝑗 match, move indices for both strings 𝑖 + 1 and 𝑗 + 1.
• Move the index 𝑖 + 1 for 𝑠𝑡𝑟𝑖𝑛𝑔 1.
• Move the index 𝑗 + 1 for 𝑠𝑡𝑟𝑖𝑛𝑔 2.

𝑡𝑜𝑝𝐷𝑜𝑤𝑛(𝑠𝑡𝑟1, 𝑠𝑡𝑟2, 𝑖 + 1, 𝑗, 𝑚𝑒𝑚𝑜)

𝑟𝑒𝑠𝑢𝑙𝑡 → 𝑡𝑜𝑝𝐷𝑜𝑤𝑛(𝑠𝑡𝑟1, 𝑠𝑡𝑟2, 𝑖 + 1, 𝑗 + 1, 𝑚𝑒𝑚𝑜)
𝑡𝑜𝑝𝐷𝑜𝑤𝑛(𝑠𝑡𝑟1, 𝑠𝑡𝑟2, 𝑖, 𝑗 + 1, 𝑚𝑒𝑚𝑜)

72
 Step 3. Choose Optimal Solution
After coming from recursive calls, we choose an optimal solution among these calls and add the
value for the current state.

𝐹(𝑖 + 1, 𝑗 + 1) + 1
𝐹(𝑖, 𝑗) = 𝑚𝑎𝑥 < 𝐹(𝑖 + 1, 𝑗) ?
𝐹(𝑖, 𝑗 + 1)

We get the maximum among all recursive calls and add one if characters at indices 𝑖 and 𝑗 match,
meaning that we are increasing the longest common subsequence by one.

𝑡𝑜𝑝𝐷𝑜𝑤𝑛(𝑠𝑡𝑟1, 𝑠𝑡𝑟2, 𝑖 + 1, 𝑗, 𝑚𝑒𝑚𝑜)

𝑟𝑒𝑠𝑢𝑙𝑡 → 𝑚𝑎𝑥 <𝑡𝑜𝑝𝐷𝑜𝑤𝑛(𝑠𝑡𝑟1, 𝑠𝑡𝑟2, 𝑖 + 1, 𝑗 + 1, 𝑚𝑒𝑚𝑜) + 1?
𝑡𝑜𝑝𝐷𝑜𝑤𝑛(𝑠𝑡𝑟1, 𝑠𝑡𝑟2, 𝑖, 𝑗 + 1, 𝑚𝑒𝑚𝑜)

Step 4. Base Case

When we reach a base case, we need to quit a recursive function. The base case can be a base state
or case when a sub-problem is no longer valid (in this case, when it returns the worst result).

When the index for at least one of the strings reaches a string length, the function reaches the base
case.

if (i == text1.length() || j == text2.length()) {
return 0; // base case
}

Step 5. Memoization
We use transforming state variables for memorization.

The index 𝑖 for 𝑠𝑡𝑟𝑖𝑛𝑔 1 and the index 𝑗 for 𝑠𝑡𝑟𝑖𝑛𝑔 2 are state variables transforming each state. We
can use them for memoization.

if (memo[i][j] != -1) {
return memo[i][j];
}

Step 6. Return Result

Return a result of a recursive function.

73
return result

Solution

int topDown(string& text1, string& text2, int i, int j, vector<vector<int>>& memo) {

if (i == text1.length() || j == text2.length()) {
return 0; // base case
}

if (memo[i][j] != -1) {
return memo[i][j];
}

int result = INT_MIN;

if (text1[i] == text2[j]) {
result = max(result, topDown(text1, text2, i+1, j+1, memo) + 1);
}

result = max({result, topDown(text1, text2, i+1, j, memo), topDown(text1, text2, i,

j+1, memo)});

memo[i][j] = result;

return result;
}

Analysis

Time-Complexity: 𝑂(𝑛𝑚)

We are calling the function three times and have a total of 𝑛𝑚 states, where 𝑛 is the length of 𝑠𝑡𝑟𝑖𝑛𝑔 1
and 𝑚 is the length of 𝑠𝑡𝑟𝑖𝑛𝑔 2.

Space-Complexity: 𝑂(𝑛𝑚)

We are using 𝑛𝑚 space to store sub-state solutions.

Bottom-Up

Step 1. Base Case

Find a base case for a given problem.

74
For the base case, assume that both strings are empty. In that case, the longest common subsequence
we can get is 0.

int dp[n+1][m+1];
memset(dp, 0, sizeof(dp));

Step 2. Move Toward a Target State

Starting from a base case, we move toward a target state.

We need to iterate over both of the strings to compare characters at indices 𝑖 and 𝑗.

for (int i = 1; i <= n; ++i) {

for (int j = 1; j <= m; ++j) {
/* code */
}
}

Step 3. Iterate Over Options

For every step (state), we have several options (ways) to choose to come to the current state. We
need to iterate all possible options to find the most optimal solution for the current state.

For each state, there are three options to come to the current state:
• If characters at these indices 𝑖 and 𝑗 match, we get the possible best result if we ignore these
characters (𝑖 − 1, 𝑗 − 1).
• If characters at these indices don’t match, we get the possible best result if we ignore the
current character of 𝑠𝑡𝑟𝑖𝑛𝑔 1 (𝑖 − 1, 𝑗).
• If characters at these indices don’t match, we get the possible best result if we will ignore the
current character of 𝑠𝑡𝑟𝑖𝑛𝑔 2 (𝑖, 𝑗 − 1).

𝑑𝑝[𝑖 − 1][𝑗 − 1]
𝑑𝑝[𝑖][𝑗] → 𝑑𝑝[𝑖 − 1][𝑗]
𝑑𝑝[𝑖][𝑗 − 1]

Step 4. Choose an Optimal Solution

We find an optimal solution (maximum, minimum, shortest, longest, etc.) without the current state
and add a value for the current state.

75
If characters at indices 𝑖 and 𝑗 match, we add one for the current state, and we find the maximum
among all options.

for (int i = 1; i <= n; ++i) {

for (int j = 1; j <= m; ++j) {
if (text1[i-1] == text2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
}
dp[i][j] = max({dp[i][j], dp[i-1][j], dp[i][j-1]});
}
}

Step 5. Return Result

After reaching a target state, return an answer for the target state.

We return the answer for the target state.

return dp[n][m]

Solution

int bottomUp(string text1, string text2) {

int n = (int)text1.length();
int m = (int)text2.length();

int dp[n+1][m+1];

memset(dp, 0, sizeof(dp));

for (int i = 1; i <= n; ++i) {

for (int j = 1; j <= m; ++j) {
if (text1[i-1] == text2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
}
dp[i][j] = max({dp[i][j], dp[i-1][j], dp[i][j-1]});
}
}

return dp[n][m];
}

76
Analysis

Time-Complexity: 𝑂(𝑛𝑚)

Inside the nested loop, we are performing constant 𝑂(1) operations 𝑛𝑚 times, where 𝑛 is the length of
𝑠𝑡𝑟𝑖𝑛𝑔 1 and 𝑚 is the length of 𝑠𝑡𝑟𝑖𝑛𝑔 2.

Space-Complexity: 𝑂(𝑛𝑚)

We are using 𝑛𝑚 space to store sub-state solutions.

77
Best Time to Buy and Sell Stock

Given an array of stock prices on a given day, find the maximum profit you can make by buying and
selling stocks. You are allowed to participate in one transaction at a time (you can sell only if you buy
before).

Intuition

For every stock in the array, we need to make a decision that will lead to the maximum profit. We
need to decide to sell, buy or ignore a stock on the current day.

Top-Down

Step 1. Iterate Over Options

When we solve a problem recursively, for every sub-problem (state), we have different options
(directions) to choose to reach our target. We need to iterate over all possible options to find the
most optimal solution.

For each day (state), there are three options to choose from:
• Sell a stock if we have one.
• Ignore the current stock.
• Buy the current stock.

Step 2. Reduce Target

Choosing every option, we reduce a target to a particular value, and we call a recursive function
again with the new updated target.

For each day (state), we choose one of the available options:

• If we already have bought a stock, we can sell it.
• We can decide not to perform any operation on this day.
• We can buy a stock on this day.

𝑠𝑒𝑙𝑙
𝑟𝑒𝑠𝑢𝑙𝑡 → 𝑠𝑘𝑖𝑝
𝑏𝑢𝑦

int sell = topDown(prices, index+1, false, memo).

int skip = topDown(prices, index+1, canSell, memo);
int buy = topDown(prices, index+1, true, memo)

78
 Step 3. Choose Optimal Solution
After coming from recursive calls, we choose an optimal solution among these calls and add the
value for the current state.

We have the following available options:

• If we sell a stock, we earn 𝑝𝑟𝑖𝑐𝑒𝑠[𝑑𝑎𝑦] on this day.
• If we decide not to perform any operation on this day, the profit will not change.
• If we buy a stock on this day, we pay 𝑝𝑟𝑖𝑐𝑒𝑠[𝑑𝑎𝑦] .

We choose the best option among the options above.

int sell = maxProfit(prices, index+1, sold+1, bought, memo) + prices[index];

int skip = maxProfit(prices, index+1, sold, bought, memo); .
int buy = maxProfit(prices, index+1, 0, bought, memo) - prices[index];
int result = max({buy, sell, skip});

Step 4. Base Case

When we reach a base case, we need to quit a recursive function. The base case can be a base state
or case when a sub-problem is no longer valid (in this case, when it returns the worst result).

We reach the base case when we iterate over all days.

if (index >= prices.size()) {

return 0;
}

Step 5. Memoization
We use transforming state variables for memorization.

The 𝑖𝑛𝑑𝑒𝑥 of the day and the possibility to sell stock 𝑐𝑎𝑛𝑆𝑒𝑙𝑙 are state variables transforming each
state. We can use them for memoization.

if (memo[index][canSell] != -1) {
return memo[index][canSell];
}

79
 Step 6. Return Result
Return a result of a recursive function.

return result

Solution

int topDown(vector<int>& prices, int index, bool canSell, vector<vector<int>>& memo) {

if (index >= prices.size()) {
return 0;
}

if (memo[index][canSell] != -1) {
return memo[index][canSell];
}

int sell = INT_MIN;

int buy = INT_MIN;

if (canSell) {
// can sell a product
sell = maxProfit(prices, index+1, false, memo) + prices[index];
} else {
// can buy a product
buy = maxProfit(prices, index+1, true, memo) - prices[index];
}

int skip = maxProfit(prices, index+1, canSell, memo);

int result = max({buy, sell, skip});

memo[index][canSell] = result;

return result;
}

Analysis

Time-Complexity: 𝑂(𝑛)

We call the function three times and have a total of 𝑛 states, where 𝑛 is the number of days.

Space-Complexity: 𝑂(𝑛)

We are using 𝑛 space to store sub-state solutions.

80
Bottom-Up

Step 1. Base Case

Find a base case for a given problem.

The base cases are two options for the first day:
• Buy on the first day and pay 𝑝𝑟𝑖𝑐𝑒𝑠[0].
• Sell and earn on the first day. But on the first day, there isn’t any stock to sell, so the profit is 0.

dp[0][0] = -prices[0]; // 0 - buy

dp[0][1] = 0; // 1 - sell

Step 2. Move Toward a Target State

Starting from a base case, we move toward a target state.

We iterate over prices to make the maximum profit.

for (int i = 1; i < prices.size(); ++i) {

/* code */
}

Step 3. Iterate Over Options

For every step (state), we have several options (ways) to choose to come to the current state. We
need to iterate all possible options to find the most optimal solution for the current state.

For every state, there are three options to come to the current state:

• If you decide to buy new stock, consider the case when you previously sold a stock and update
it with a new price.

dp[i][0] = dp[i-1][1] - prices[i]

• If you decide to sell a stock, consider the case when you previously bought the stock and
update it with a new price.

dp[i][1] = dp[i-1][0] + prices[i]

• Ignore the current state (use the previous state when you bought or sold a stock).

81
 dp[i][0] = dp[i-1][0]
dp[i][1] = dp[i-1][1]

Step 4. Choose an Optimal Solution

We find an optimal solution (maximum, minimum, shortest, longest, etc.) without the current state
and add a value for the current state.

We find the maximum among all available options.

dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])

dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])

Step 5. Return Result

After reaching a target state, return an answer for the target state.

We return the answer for the target state.

return dp[n-1][1]

Solution

int bottomUp(vector<int>& prices) {

if (prices.size() == 0) {
return 0;
}

int n = (int)prices.size();

vector<vector<int>> dp(n, vector<int> (2));

dp[0][0] = -prices[0];
dp[0][1] = 0;

for (int i = 1; i < prices.size(); ++i) {

dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]);
dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);
}

return dp[n-1][1];
}

82
Analysis

Time-Complexity: 𝑂(𝑛)

Inside the single loop, we are performing constant 𝑂(1) operations 𝑛 times, where 𝑛 is the total
number of days.

Space-Complexity: 𝑂(𝑛)

We are using 𝑛 space to store sub-state solutions.

83
Nim Game

Given a pile of stones and two players, each player can remove 1 to 5 stones in one move. The
player who will remove the last stone will win. Find out whether player 1 can win the game.

𝑛 − 𝑎 𝑡𝑜𝑡𝑎𝑙 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑠𝑡𝑜𝑛𝑒𝑠, 𝑎𝑛𝑑 𝑔𝑟𝑒𝑎𝑡𝑒𝑟 𝑡ℎ𝑎𝑛 0

𝑘 − 𝑎 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑠𝑡𝑜𝑛𝑒𝑠 𝑐𝑎𝑛 𝑏𝑒 𝑟𝑒𝑚𝑜𝑣𝑒𝑑

Intuition

We simulate the game and find out the case when player 2 loses the game.

Top-Down

Step 1. Iterate Over Options

When we solve a problem recursively, for every sub-problem (state), we have different options
(directions) to choose to reach our target. We need to iterate over all possible options to find the
most optimal solution.

There are options to remove 1 to 𝑘 stones for every state, where 𝑘 is the maximum number of stones,
5. We iterate over these options to find out the case that leads to the win.

for (int i = 1; i <= k; ++i) {

/* code */
}

Step 2. Reduce Target

Choosing every option, we reduce a target to a particular value, and we call a recursive function
again with the new updated target.

We try to remove 1 to 𝑘 stones for every state and call a recursive function with the new updated
target.

for (int i = 1; i <= k; ++i) {

topDown(n - i, k);
}

84
 Step 3. Choose Optimal Solution
After coming from recursive calls, we choose an optimal solution among these calls and add the
value for the current state.

After coming from recursive calls, check if one of the options leads to losing the game. If the option
leads to losing the game, we will leave this option for player 2. Consequently, player 1 will win if we will
choose this option.

for (int i = 1; i <= k; ++i) {

if (!topDown(n - i, k)) {
return true;
}
}

Step 4. Base Case

When we reach a base case, we need to quit a recursive function. The base case can be a base state
or case when a sub-problem is no longer valid (in this case, when it returns the worst result).

The base case is the case when the game is over.

if (n <= k) {
return true;
}

Step 5. Memoization
We use transforming state variables for memorization.

𝑛 is a state variable transforming at each state. We can use it for memoization.

if (memo[n] != -1) {
return memo[n] == 1;
}

Step 6. Return Result

Return a result of a recursive function.

85
Solution

// n - a total number of stones

// k - a number of stones can be removed

bool topDown(int n, int k) {

if (n <= k) {
return true;
}

if (memo[n] != -1) {
return memo[n] == 1;
}

for (int i = 1; i <= k; ++i) {

if (!topDown(n - i, k)) {
memo[n] = 1;
return true;
}
}

memo[n] = 0;

return false;
}

Analysis

Time-Complexity: 𝑂(𝑛𝑘)

We call the function 𝑘 times and have a total of 𝑛 states, where 𝑛 is the total number of stones and 𝑘 is
the number of stones that can be removed.

Space-Complexity: 𝑂(𝑛)

We are using 𝑛 space to store sub-state solutions.

Bottom-Up

Step 1. Base Case

Find a base case for a given problem.

Find the base cases for cases we can predict the result.

86
dp[1] = true;
dp[2] = true;
dp[3] = true;
...
dp[k] = true;

Step 2. Move Toward a Target State

Starting from a base case, we move toward a target state.

We find the scenarios for every amount of stone from 1 to 𝑛 stones.

for (int i = k+1; i <= n; ++i) {

/* code */
}

Step 3. Iterate Over Options

For every step (state), we have several options (ways) to choose to come to the current state. We
need to iterate all possible options to find the most optimal solution for the current state.

For every state, we try to remove 1 to 𝑘 stones and consider the case with removed stones.

for (int i = k+1; i <= n; ++i) {

for (int j = 1; j <= k; ++j) {
dp[i-j];
}
}

Step 4. Choose an Optimal Solution

We find an optimal solution (maximum, minimum, shortest, longest, etc.) without the current state
and add a value for the current state.

If the state with removed stones leads to losing the game, then player 1 wins the game. Otherwise,
player 1 loses the game.

for (int i = k+1; i <= n; ++i) {

for (int j = 1; j <= k; ++j) {
if (!dp[i-j]) {
dp[i] = true;

87
 }
}
}

Step 5. Return Result

After reaching a target state, return an answer for the target state.

We return the answer for the target state.

return dp[n]

Solution

// n - a total number of stones

// k - a number of stones can be removed

bool bottomUp(int n, int k) {

if (n <= k) {
return true;
}

vector<int> dp(n+1, false);

for (int i = 1; i <= k; ++i) {

dp[i] = true;
}

for (int i = k+1; i <= n; ++i) {

for (int j = 1; j <= k; ++j) {
if (!dp[i-j]) {
dp[i] = true;
}
}
}

return dp[n];
}

88
Analysis

Time-Complexity: 𝑂(𝑛𝑘)

Inside the nested loop, we are performing constant 𝑂(1) operations 𝑛𝑘 times, where 𝑛 is the total
number of stones and 𝑘 is the number of stones that can be removed.

Space-Complexity: 𝑂(𝑛)

We are using 𝑛 space to store sub-state solutions.

89