# Dynamic Programming

## Steps

1. brute force recursive solution
• goes through every possibility
• no global variables
• no tail recursion
• don’t have unnecessary variables
2. analyze solution
• if solution is recursive then it has an optimal substructure
• find if there are overlapping sub-problems
• same function with same input
3. figure out sub problems
• memoize the sub problems that you are solving more than once
4. switch to bottom-up solution
• this can improve the solution, but might not
• switch from recursive to iterative

Dynamic programming is similar to divide and conquer

For any problem where you are asked to find the most/least/largest/smallest etc, an excellent technique is to compare every possible combination.

https://www.quora.com/What-is-the-difference-between-dynamic-programming-and-divide-and-conquer

http://www.flawlessrhetoric.com/Dynamic-Programming-First-Principles

Use dynamic programming when there is optimal substructure and overlapping subproblems.

Dynamic programming is useful when you’re trying to optimize something given a constraint. Dynamic programming only works when each subproblem is discrete; when it doesn’t depend on other subproblems.

• Every dynamic-programming solution involves a grid.
• The values in the cells are usually what you’re trying to optimize. For the knapsack problem, the values were the value of the goods.
• Each cell is a subproblem, so think about how you can divide your problem into subproblems. That will help you figure out what the axes are.
• There’s no single formula for calculating a dynamic-programming solution.

each sub-problem is solved only once. There is no recursion. The key in dynamic programming is remembering. That is why we store the result of sub-problems in a table so that we don’t have to compute the result of a same sub-problem again and again.

the very first time a subproblem is solved it’s results are tabulated(stored in some efficient datastructure) and the next time it is encountered instead of solving it again, the result is simply looked up in the table and returned.

knapsack problem, Matrix Chain Multiplication, Tower of Hanoi puzzle, etc..

frequently use the `Math.max` function

## Longest Common Substring

``````if word_a[i] == word_b[j]: #The letters match.
cell[i][j] = cell[i-1][j-1] + 1
else: #The letters don’t match.
cell[i][j] = 0
``````

## Longest Common Subsequence

``````if word_a[i] == word_b[j]: # The letters match.
cell[i][j] = cell[i-1][j-1] + 1
else: # The letters don’t match.
cell[i][j] = max(cell[i-1][j], cell[i][j-1])
``````

Levenshtein distance is used for string similarity

## Largest subarray sum

Find largest sum of any sub array in an array of ints

O(n) time, O(1) space

``````int maxSum(int[] inp) {
int max;
int lm;
for (i=0; i<inp.length; i++;) { // iterate through array
lm = Math.max(inp[i]+lm, 0); // restart local max if next item takes it below zero
max = Math.max(lm, max); // update max if local max exceeds it
}
return max;
}
``````

## Memoization

Memoization ensures that a function doesn’t run for the same inputs more than once by keeping a record of the results for the given inputs (usually in a hash map).

### Python

https://www.interviewcake.com/concept/python/memoization

``````  class Fibber:
def __init__(self):
self.memo = {}
def fib(self, n):
if n < 0:
raise Exception("Index was negative. No such thing as a negative index in a series.")
# base cases
elif n in [0, 1]:
return n
# see if we've already calculated this
if n in self.memo:
print "grabbing memo[%i]" % n
return self.memo[n]
print "computing fib(%i)" % n
result = self.fib(n - 1) + self.fib(n - 2)
# memoize
self.memo[n] = result
return result
``````

## Bottom up

https://www.interviewcake.com/concept/python/bottom-up?

Avoids recursion so that a large call stack isn’t built up

Starts at the beginning or base case, recursion usually starts at the end

Starts a base case and does iteration instead of recursion, usually more space efficient.

build a cache/hashtable/array of the solution, and return the best/correct item in the cache

## Sticks problem

https://www.hackerrank.com/challenges/newyear-present/problem?h_r=next-challenge&h_v=zen&isFullScreen=true

intsThatAddUpToInt(int input, Map map) // for each in map // while there (input-i) // pop // add to list

do the math at the end. get the counts of each stick and multiply to find the number combos