Tags

  • AWS (7)
  • Apigee (3)
  • ArchLinux (5)
  • Array (6)
  • Backtracking (6)
  • BinarySearch (6)
  • C++ (19)
  • CI&CD (3)
  • Calculus (2)
  • DesignPattern (43)
  • DisasterRecovery (1)
  • Docker (8)
  • DynamicProgramming (20)
  • FileSystem (11)
  • Frontend (2)
  • FunctionalProgramming (1)
  • GCP (1)
  • Gentoo (6)
  • Git (15)
  • Golang (1)
  • Graph (10)
  • GraphQL (1)
  • Hardware (1)
  • Hash (1)
  • Kafka (1)
  • LinkedList (13)
  • Linux (27)
  • Lodash (2)
  • MacOS (3)
  • Makefile (1)
  • Map (5)
  • MathHistory (1)
  • MySQL (21)
  • Neovim (10)
  • Network (66)
  • Nginx (6)
  • Node.js (33)
  • OpenGL (6)
  • PriorityQueue (1)
  • ProgrammingLanguage (9)
  • Python (10)
  • RealAnalysis (20)
  • Recursion (3)
  • Redis (1)
  • RegularExpression (1)
  • Ruby (19)
  • SQLite (1)
  • Sentry (3)
  • Set (4)
  • Shell (3)
  • SoftwareEngineering (12)
  • Sorting (2)
  • Stack (4)
  • String (2)
  • SystemDesign (13)
  • Terraform (2)
  • Tree (24)
  • Trie (2)
  • TwoPointers (16)
  • TypeScript (3)
  • Ubuntu (4)

    • Home

    [Dynamic Programming] Memoization & Tabulation Recipe

    Published Nov 06, 2021 [  DynamicProgramming  ]

    Recursion

    1. Think of the base case, and what to return in base case
    2. Think how we can reduce the problem size, and use recursion to solve the sub-problem.

    Memoization

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

    Tabulation

    1. visualize the problem as a table
    2. size the table based on the inputs
    3. initialize the table with default value
    4. seed the trivial answer into the table
    5. iterate through the table
    6. fill further position based on the current position

    Reference