Skip to main content

Introduction

Summary

keywords

TODO

HW

Exercise*

Next time solution of Knapsack problem.

Recap

master's theorem, asymptotic notations, substitutions

what algorithms did we learn? linear search, binary search, all kinds of sorting,

Contents Forward

  • DP or Greedy
  • Fibonacci
  • Zero one, unbounded, simple knapsack
  • matrix chain multiplication
  • longest common subsequence

write in resursive first, and convert to DP algorithm.

Dynamic Programming

  • used for solving Optimizing Problem; minimize or maximize sth. memo. optimization can be solved using Greedy and DP.
  • reduces time complexity of prior algorithms.
  • should try all possible solutions and pick up the best solution.

Two approach of DP​

  • memoization(Top down).
  • Tabulation (Bottom up).

How do you identify the problem can be solved by DP?​

to implement, the problem should contain overlapping subproblems. DP follows Principle of Optimality

principle of optimality​

problems can be solved by taking a sequence of decision.

Divide n Conquer vs. DP​

similarity : combine subproblem solution to make final solution difference : Divide n Conquer when disjoint subproblems, there will be no same call with same input. ex. merge sort. DP when overlapping subproblems. ex. fibonacci.

Greedy vs. DP​

  • Greedy sees the local optimum.
  • Greedy do not deal with multiple possible solutions
  • Greedy do not guarantee the correct answer.
  • Greedy is faster.
  • Greedy deal with some uncertain assumptions.

#todo : see slide 5. (see image)

memo. Greedy Greedy is based on local optimum. step by step,

Problem w/ Recursion; Why do we need DP?​

stack overflow.

DP#1, Fibonacci.

Fibonacci in Memoization​

recursive approach, top-down approach.

Steps.

  1. initialize an 1D array (with invalid results, like -1).
  2. after calling functions, fill the result on array.
  3. When overlapping functions, refer the array and get the result w/o calculating.

Still recursive.

Fibonacci in Tabulation​

iterative approach, using loops.

Steps.

  1. make an array.
  2. iterating from 0 to desitnation, calculate each fibonacci one by one.

DP#2-1, 0/1 Knapsack.

bag with a finite capacity bag. each item has weight and price. maximize the contained price of the bag.

Take, or don't take the item.