Verified Dynamic Programming with Σ-types in Lean
https://tannerduve.github.io/blog/memoization-sigma/
#HackerNews #Verified #Dynamic #Programming #Σ-types #Lean #DynamicProgramming #LeanLang
Verified Dynamic Programming with Σ-types in Lean
1. IntroductionIf you’ve taken an algorithms class, you have likely seen dynamic programming, specifically a technique called memoization. Memoization works to optimize recursive algorithms by caching the solutions to subproblems in a table, and when a subproblem is encountered, it queries the table instead of recomputing the solution. This gives us an exponential performance boost.





