# Dynamic Programming Patterns to Ace Interviews

Following materials are taken from freecodeCamp.org Youtube video course https://www.youtube.com/watch?v=oBt53YbR9Kk strongly recommend to watch the video!

Python version Colab Notebook @ https://colab.research.google.com/gist/Mageswaran1989/658eb75fed28f5953ac5167b3a14ff6d/dynamicprogramming.ipynb

Online Visualisation Tools:

Dynamic Programming is useful when a problem as repetitive computation that can be cached. When cached the repetitive computation is inferred from the memory and thus reduces overall time taken to compute the solution.

## Recursion Memoization

- Visualise the problem as a tree
- Implement the tree using recursion
- Test it
- Add memo object
- Add a base case to return memo values

## Array Tabulation

- TODO for later time :)

Once the underlying patterns in DP problems is recognised, with practice its easy to get a hang of them.

Types:

- Return one final value
- Decision Problem (True/False)
- Find a combination that matches given requirements
- Finding a optimised solution in the combination

Tricks:

- Remember the base case return type and final return should be the same
- When one of the inputs happened to be list of values, then there is gonna be a
`for...loop`

in the recursion - When
`for...loop`

is involved, visualise what happens the last leaf nodes and build the result backwards

1**One final value**

Find a final result value for a given problem which can have repetitive intermediate computation.

# Fibonacci Sequence

`Base cases:`

n < 0: Return n

fib(n) : fib(n-1) + fib(n-2)

Runtime: O(2^n)

Space: O(n)

`def fib(n, memo = {}):`

** if n in memo:**

return memo[n]

if n <= 1:

return n

else:

# calculate for first time

**memo[n] = fib(n-1, memo) + fib(n-2, memo)**

return memo[n]

Runtime: O(n)

Space: O(n)

Find a final result value for a given problem with multiple inputs, again which can have repetitive intermediate computations.

# Grid Traveller

Say that you are a traveller on a 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 dimension m * n?

Write a function **grid_traveller(m, n)** that calculates this.

`Base cases:`

m or n ≤ 0 : When there is no cell to move return 0

m and n = 1 : When there is only one cell return 1

memo(m,n) = memo(m-1, n) + memo(m, n-1)

Time: O(2^n+m)

Space: O(n+m)

def grid_travel(m,n, memo={}):

"""

:paramm: Total number of rows

:paramn: Total number of columns

:return:

"""

# make the key with m & n, to differentiate rows and colsf"m{m}n{n}"

key =if key in memo:

return memo[key]

if (m == 1 and n==1):

return 1

elif (m ==0 or n ==0):

return 0

else:

memo[key] = grid_travel(m-1, n, memo) + grid_travel(m, n-1, memo)

return memo[key]

Time: O(n * m)

Space: O(n+m)

2** Decision Problem**

Return a true or false after exploring all possible solution space

## canSum

Write a function `canSum(target_sum, numbers)`

that takes in a target sum and an array of numbers as arguments.

The function should return a boolean indicating whether or not it is possible to generate the target sum using numbers from the array.

You may use an element of the array as many times as needed and al inputs are non negative

m = target sum , n = array length

Time: O(n^m)

Space: O(m)

def can_sum(target_sum, values, memo={}):

""":param target_sum:

:param values: list

:return:

"""

# print(memo, values)

if target_sum in memo:

return memo[target_sum] if target_sum == 0:

return True

if target_sum < 0:

return Falsefor value in values:

reminder = target_sum - value

if can_sum(reminder, values, memo):# If no way leads to zero then there is no possible values leads to sum

memo[target_sum] = True

return True

memo[target_sum] = False

return False

m = target sum , n = array length

Time: O(n*m) branch for every choice of number in the list of length

`n`

Space: O(m)

## Can Construct

Write function `can_construct(target, word_bank)`

that accepts a target string and an array of strings

The function should return a boolean indicating whether or not the `target`

can be constructed by concatenating elements of the `word_bank`

array.

You may reuse elements of `word_bank`

as many times as needed

m = target word length , n = word bank length

Time: O(n^m * m)

`branches for each element in the list and`

n`subtract operation in each branch and`

m`operation to slice array`

mSpace: O(m*m)

`m`

for stack depth and`m`

for to store sliced array

def can_construct(target, word_bank, memo={}): if target in memo:

return memo[target] if target == '':

return True # When we found a way reconstruct the string # Return true if any of branch returns true

for word in word_bank:# If no branch leads to positive case, return false

# check for matching prefix

if target.startswith(word):

suffix = target[len(word):]

if can_construct(suffix, word_bank):

memo[suffix] = True

return True

memo[target] = False

return False

m = target word length , n = word bank length

Time: O(n * m * m)

`branches for each element in the list and`

n`subtract operation in each branch and`

m`operation to slice array`

mSpace: O(m*m)

`for stack depth and`

m`for to store sliced array`

m

3** Combination Problem**

Find possible combination for given target and list of possible values.

## How Sum

Write a function `how_much(target_sum, numbers)`

, that takes in a target_sum and an array of numbers as arguments.

The function should return an array containing any combination of elements that add up to exactly the target sum. If there is no combination that adds up to the target sum, return null.

If there are multiple combinations possible, you may return any single one.

m = target sum , n = array length

Time: O(n^m * m)

`branches for each element in the list and`

n`subtract operation in each branch and`

m`operation to copy the array into result array`

mSpace: O(m)

def how_sum(target_sum, values, memo={}):

if target_sum in memo:

return memo[target_sum] if target_sum == 0:

return []

if target_sum < 0:

return Nonefor value in values:memo[target_sum] = None

ret = how_sum(target_sum - value, values, memo)

if ret is not None:

ret.append(value)

memo[target_sum] = ret

return ret

return None

m = target sum , n = array length

Time: O(n*m²)

Space: O(m²)

## Count Construct

Write a function `count_construct(target, word_bank)`

taht accepts a target string and an array of strings.

The function should return the number of ways that the target can be constructed by concatenating elements of the word_bank array.

You may reuse elements of word_bank as many time as needed.

m = target word length , n = word bank length

Time: O(n^m * m)

`branches for each element in the list and`

n`subtract operation in each branch and`

m`operation to slice array`

mSpace: O(m*m)

`for stack depth and`

m`for to store sliced array`

m

def count_contruct(target, word_bank, memo={}): if target in memo:

return memo[target] if len(target) == 0 :

return True total_ways = 0

for word in word_bank:

if target.startswith(word):

suffix = target[len(word):]

total_ways += count_contruct(suffix, word_bank)

memo[target] = total_ways

return total_ways

m = target word length , n = word bank length

Time: O(n * m * m)

`branches for each element in the list and`

n`subtract operation in each branch and`

m`operation to slice array`

mSpace: O(m*m)

`for stack depth and`

m`for to store sliced array`

m

4 Optimisation Problem

Find all possible combination for given target and list of possible values and return the best one

## Best Sum

Write a function `best_sum(target_sum, numbers)`

that takes in a target sum and an array of numbers as arguments.

The function should return an array containing the shortest combination of numbers that add up to exactly the target sum.

If there is a tie for the shortest combination, you may return any on of the shortest

m = target sum , n = array length

Time: O(n^m * m)

`branches for each element in the list and`

n`subtract operation in each branch and`

m`operation to copy the array into result array`

mSpace: O(m²)

def best_sum(target_sum, values, memo): if target_sum in memo:

return memo[target_sum] if target_sum == 0:

return [] if target_sum < 0:

return None best_pair = Nonefor value in values:memo[target_sum] = best_pair

ret = best_sum(target_sum=target_sum - value, values=values, memo=memo)

if ret is not None:

res = ret + [value]

if best_pair is None or len(res) < len(best_pair):

best_pair = res

memo[target_sum] = best_pair

# return best_pair # Dont return the value until all possible combinations are evaluated for child tree

return memo[target_sum]

m = target sum , n = array length

Time: O(n*m²)

Space: O(m²)

## All Construct

Write a function `all_construct(target, word_bank)`

that accepts a target string and an array of strings

The function should return a 2D array containing all of the ways that the target can be constructed by concatenating elements of the word bank array. Each element of the 2D array should represent one combination that constructs the target.

You may reuse elements of the word bank as many times as needed.

def all_construct(target, word_bank, memo={}): if target in memo:

return memo[target] if target in memo:

return memo[target] if target == '':

return [[]] res = []for word in word_bank:memo[target] = res return res

if target.startswith(word):

suffix = target[len(word):]

suffix_ways = all_construct(suffix, word_bank)

target_ways = list(map(lambda l: l + [word], suffix_ways))

res.extend(target_ways)

m = target word length , n = number of words in word bank length

Time: O(n^m ) If complexity is exponential i.e m^n then we can ignore additional complexity like slicing the array

Space: O(m)

Test your understanding….