ThinkerQAQ

NOTE

3.2 Dynamic Programming

Dynamic programming steps and a path-counting example.

Data Structures & AlgorithmsCreated Updated 1 min readhistorical

This is a historical learning note and may contain outdated or incomplete understanding.

1. Dynamic Programming Steps

  1. Recursion + memoization -> recurrence
  2. State definition: opt[n],dp[n],fib[n]
  3. State transition equation: opt[n]=best_of(opt[n-1], opt[n-2], ...)
  4. Optimal substructure

2. Example

2.1. Path Count Calculation

  • Recursion
  • Recurrence

Discussion

Sign in with GitHub to comment. Discussions are stored as GitHub Issues.View on GitHub