Dynamic Programming & Recursion

Dynamic Programming

The idea with dynamic programming is to trade time for space. This is only applicable if you have repeated subproblems. Instead of recomputing subproblems over and over, use space to save answers to subproblems so you can look them up later.

Dynamic programming combines the beast of both worlds.

Recursion

Laws

  • A recursive algorithm must have a base case.
  • A recursive algorithm must change its state and move toward the base case.
  • A recursive algorithm must call itself, recursively.

Steps

  1. Keeping in mind what the function should do, not what it currently does
  2. Identifying the proper subproblems
  3. Use the solution to your subproblems to solve the original problem
  4. Writing a base case - interesting, i was always trying to identify the base case first, but it does make since to start with code, then nail the base case as your simplist case.

other steps

  1. Order your data - Whatever data we are operating on, whether it is numbers, strings, lists, binary trees or people, it is necessary to explicitly find an appropriate ordering that gives us a direction to move in to make the problem smaller.

Related Notes