Dynamic Programming

Question 1

DP

Answer 1

We can apply DP in following patters

• Overlapping subproblems
  
  • if we solve the problem by solving subproblems, we can reuse the already solved subproblem solution.
• Optimal structure
  
  • while solving the subproblem, we can choose the efficient/option solution of subproblem to solve the bigger problem.

Question 2

Data structure/Methods to use

Answer 2

• Memoization ( Top -Down approach)
  
  • build solution and store the results as we solve.
    -Tabulation ( Bottom -Up approach)
    build solution from lower level and store the results.