Dynamic Programming & Recursion
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.
- 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.
- Keeping in mind what the function should do, not what it currently does
- Identifying the proper subproblems
- Use the solution to your subproblems to solve the original problem
- 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.
- 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.