Engrain by ByteRush

DSA.12 3 concepts

Backtracking and dynamic programming

Enumerate with backtracking and optimise with DP.

  1. DSA.12.01Pattern 17: BacktrackingCoreMid-levelBeing written
  2. DSA.12.02Pattern 18a: Dynamic programming — 1DCoreMid-levelBeing written
  3. DSA.12.03Pattern 18b: Dynamic programming — 2D and knapsackSeniorBeing written

Interview questions in this module

  1. How do you recognise a DP problem?
  2. Top-down vs bottom-up DP: trade-offs?
  3. Generate all subsets of a set. What is the complexity?
  4. Solve coin change. Explain the state and transition.
  5. What is the difference between backtracking and DP?