Recursion and Dynamic Programming Flashcards Preview

Cracking the Coding Interview > Recursion and Dynamic Programming > Flashcards

Flashcards in Recursion and Dynamic Programming Deck (7)
Loading flashcards...
1
Q

Hints of recursion

A

It can be built off of sub problems. Look for these problem statements “Design an algorithm to compute the nth…”, “Write code to list the first n…”, “Implement a method to compute all…”

2
Q

Bottom-Up Approach

A

We start with knowing how to solve the problem for a simple case. Then we figure out how to solve the problem for two elements, then for three elements, and so on. Think about how you can build the solution for one case off of the previous case.

3
Q

Top-Down Approach

A

Think about how we can divide the problem for case N into sub problems. Be careful of overlap between the cases.

4
Q

Half-and-half approach

A

Divide the data set in half. Think of binary search and merge sort.

5
Q

Recursive vs. Iterative Solutions

A

All recursive solutions can be implemented with an interactive solution. Recursive algorithms require at least O(n) space complexity where n is the depth of its recursion tree.

6
Q

Dynamic Programming

A

Taking recursive problems and finding the overlapping sub problems (that is, the repeated calls). You then cache those results for future recursive calls. Alternatively, you can study the pattern of the recursive calls and implement something iterative. You still cache previous work. Typically used to refer to bottom-up work, but can also refer to top-down work.

7
Q

Memorization

A

Like dynamic program, it aims to cache repeated calls in a recursive problem. However, it is specific to top-down approach.