I am currently practicing Dynamic Programming problems taught by freeCodeCamp, one of my favorite resources on the internet. freeCodeCamp Dynamic Programming - Learn to Solve Algorithmic Problems & Coding Challenges

Python Solutions in GitHub

DP Problems List

  • canSum ➡️ Can you do it? yes/no (Decision Problem)
  • howSum ➡️ How will you do it? (Combinatoric Problem)
  • bestSum ➡️ What is the best way to do it? (Optimization Problem)
  • canConstruct ➡️ Can you do it? (with strings)
  • countConstruct ➡️ How many different ways to do it? (with strings)
  • allConstruct ➡️ What are the ways to do it? (with strings)

How to solve with recursion & memoization?

  1. Make it work
    • visualize the problem as a tree
    • implement the tree using recursion
    • test it
  2. Make it efficient
    • add a memo object
    • add a base case to return memo values
    • store return values into the memo

How to solve with tabulation?

  • visualize the problem as a table
  • size the table based on the inputs
  • initialize the table with default values
  • seed the trivial answer into the table
  • iterate through the table
  • fill further positions based on the current position
TO-DO: Reexamine the space and time complexity of each solution.
TO-DO: add code pieces here
TO-DO: My understanding and summary