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

Notes

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.

sub answers might depend on other subanswers

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