Skip to main content

Dynamic Programming

note

  • all DP problems can be converted into Direct Acyclic Graph (DAG)

    • then we can solve them simply as we solve DAG problems

  • some common graph problems can also be converted to DAG

Commom Way to Solve DP​

  1. solve using Memoization
  2. if needed then convert memoization to Tablulation
  3. if need to Print Optimal Solution i. do it with memoization ii. or with table formed in Tablulation

My way to solve DP problems​

  1. Convert a DP prblem to DAG graph
  2. Topologicaly sort that DAG
  3. choose the top element of the Topologically sorted stack & then use it & after that just pop it
  4. Now use the different logic for getting the Optimal Solution like min,max,count