39 lines
1.8 KiB
Markdown
39 lines
1.8 KiB
Markdown
# dynamic-programming
|
|
|
|
Runnable companion for the ankurm.com article
|
|
[Dynamic Programming in Java for Beginners: Memoization vs Tabulation (10 Classic Problems)](https://ankurm.com/dynamic-programming-java-memoization-vs-tabulation/).
|
|
|
|
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` |
|
|
|
|
```bash
|
|
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.
|