DP fundamentals: states and transitions · 1 of 3
States and transitions
State what each table entry means, build the transition from the last choice, and fill the table in an order where every entry it reads is ready.
Books1
Links5
- Algorithms, Chapter 3: Dynamic programming Follows the Fibonacci recurrence from Sanskrit poetic meters to a slow recursion, memoization and a loop, warns against greedy shortcuts and sets out a step-by-step way to design a DP. Parts of this page adapt this chapter’s text, licensed CC BY 4.0 (creativecommons.org/licenses/by/4.0), with changed wording, examples and code. jeffe.cs.illinois.edu (opens in a new tab)
- Introduction to DP Solves Frog 1 by pushing each stone's cost forward and by pulling it from earlier stones, then lists practice from Codeforces and USACO Gold. usaco.guide (opens in a new tab)
- Introduction to Dynamic Programming Memoized and bottom-up Fibonacci, with a list of classic problems and DP practice contests. cp-algorithms.com (opens in a new tab)
- Educational DP Contest Twenty-six standard DP problems in rising difficulty. Frog 1 is problem A, and later lessons use several more. atcoder.jp (opens in a new tab)
- 动态规划基础 (Dynamic programming basics) Optimal substructure, the no-aftereffect property and overlapping subproblems, then longest common and non-decreasing subsequences. oi-wiki.org (opens in a new tab)
More links5
- CSES DP Editorialcodeforces.com (opens in a new tab)
- Constant Transition DP Introductionalgo.monster (opens in a new tab)
- DP Tutorial and Problem Listcodeforces.com (opens in a new tab)
- Errichto's Dynamic Programming Lecture (3 parts)youtu.be (opens in a new tab)
- Colin Galin - A Deep Understanding of Dynamic Programmingyoutube.com (opens in a new tab)