Dynamic programming

Recursion

  1. base class

  2. inductive step

Divide and conquer

  • Recursion doesnt exist from operational perspective?

    PC + Memory instruction + increment memory address.

  • virtual memory.

recursion vs iterative - taking an implicit stack and turing it inot explicit stack.

tail recursive -- no looking back

hypothesis

D&C where we can break it down to smaller problem. Log N. Always first recursive and then formulated iteratively. Dynamically is not Static classes.

DP: Optimal substructure + overlapping subproblem

Greedy Algorithm:

  1. Change counting problem.

Not a possible way. But the best possible way. We dont need to revisit previous solution. make a choice here at one point in time, is the best choice.

Greedy: 1. no dependence on future choices

  1. no reconsideration of choices

formulation 1: Now if it is shuffled?

formulation 2: all possible choices?

combinatoric expansion.

Optimal substructure: instead of

Overlapping subproblem:

a star. djistras -- X -> negative weight.

bellman ford --< Y negative weight>

interview scheduling

first optimital substructure second overlap - memoization

starmap.