1.8 KiB
1.8 KiB
dynamic-programming
Runnable companion for the ankurm.com article Dynamic Programming in Java for Beginners: Memoization vs Tabulation (10 Classic Problems).
Ten classic problems, each solved top-down (memoization), bottom-up (tabulation) and with a space-optimised
table. Tests cross-check every variant on random inputs, and write the transcripts the article quotes.
There is no docs/ folder on purpose: the explanations live in the article.
| Component | Version | Verified against |
|---|---|---|
| JDK | 25.0.5+8 (Temurin, LTS) | java -version |
| JUnit | 6.1.3 | maven-metadata.xml on Maven Central (latest = release) |
| Maven | 3.9.11 | mvn -version |
export JAVA_HOME=/path/to/jdk-25 && export PATH="$JAVA_HOME/bin:$PATH"
cd dynamic-programming
mvn test # 11 tests; rewrites output/01-11
./scripts/run-all.sh # also regenerates output/12 (SpaceDemo under a 48 MB heap)
./scripts/make-single-file.sh # builds DynamicProgrammingTenProblems.java: java DynamicProgrammingTenProblems.java
| # | Problem | Source |
|---|---|---|
| 1 | Fibonacci | Fibonacci |
| 2 | Climbing Stairs | ClimbingStairs |
| 3 | House Robber | HouseRobber |
| 4 | Coin Change (fewest coins, and number of ways) | CoinChange |
| 5 | Longest Increasing Subsequence | LongestIncreasingSubsequence |
| 6 | 0/1 Knapsack | Knapsack01 |
| 7 | Longest Common Subsequence | Lcs |
| 8 | Edit Distance | EditDistance |
| 9 | Unique Paths | UniquePaths |
| 10 | Partition Equal Subset Sum | PartitionEqualSubsetSum |
Captured output is in output/: 01 Fibonacci call counts, 02 Fibonacci pitfalls (computeIfAbsent, long overflow,
stack depth), 03-10 one dry run per problem, 11 the cross-check summary, 12 the heap-limited space demo.