🧨 Caching — Dynamic Programming

Dynamic programming (DP) is an unnecessarily fancy name for caching results—either on-demand or proactively, to avoids redundant computation.

🫙 Top-Down Caching —— Memoization

• Execution: Recursive
• Trigger: Compute subproblem only when needed
• Storage: Cache results as they’re encountered
• Symbolic trace: Annotated recursive tree
• Example:

  memo = {}
  def fib(n):
      if n in memo: return memo[n]
      if n <= 1: return n
      memo[n] = fib(n-1) + fib(n-2)
      return memo[n]

🫙 Bottom-Up Caching —— Tabulation

• Execution: Iterative
• Trigger: Precompute all subproblems in order
• Storage: Fill table from base cases upward
• Symbolic trace: Linear table evolution
• Example:

  def fib(n):
      dp = [0, 1] + [0]*(n-1)
      for i in range(2, n+1):
          dp[i] = dp[i-1] + dp[i-2]
      return dp[n]

🏷️ Etymology

🧠 Why “Dynamic Programming”?

• Coined by Richard Bellman in the 1950s.
• “Programming” meant planning, not coding.
• “Dynamic” referred to multi-stage decisions evolving over time.
• The term was partly chosen to sound important and non-threatening to funders.