✳flâneur — a map of the web's best reading

Introduction to Dynamic Programming - Algorithms for Competitive Programming

cp-algorithms.com · 1,557 words · saved by 1 readers

The essence of dynamic programming is to avoid repeated calculation. Often, dynamic programming problems are naturally solvable by recursion. In such cases, it's easiest to write the recursive solution, then save repeated states in a lookup table. This process is known as top-down dynamic programming with memoization. That's read "memoization" (like we are writing in a memo pad) not memorization. One of the most basic, classic examples of this process is the fibonacci sequence. Its recursive formulation is     𝑓 ( 𝑛 ) = 𝑓 ( 𝑛 − 1 ) + 𝑓 ( 𝑛 − 2 ) <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>f</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo><mo>=</mo><mi>f</mi><mo stretchy="false">(</mo><mi>n</mi><mo>−</mo><mn>1</mn><mo stretchy="false">)</mo><mo>+</mo><mi>f</mi><mo stretchy="false">(</mo><mi>n</mi><mo>−</mo><mn>2</mn><mo stretchy="false">)</mo></math> $f(n) = f(n-1) + f(n-2)$  where     𝑛 ≥ 2 <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>n</mi><

Last update: August 26, 2025 &emsp; Original Introduction to Dynamic Programming &para; The essence of dynamic programming is to avoid repeated calculation. Often, dynamic programming problems are naturally solvable by recursion. In such cases, it's easiest to write the recursive solution, then save repeated states in a lookup table. This process is known as top-down dynamic programming with memoization. That's read "memoization" (like we are writing in a memo pad) not memorization. One of the most basic, classic examples of this process is the fibonacci sequence. Its recursive formulation is

Explore this link on the map →

saved by

related reading