Package topics.dynamic

package topics.dynamic

Dynamic Programming algorithms — optimisation via overlapping sub-problems.

Dynamic Programming (DP) solves problems that exhibit two key properties:

• Optimal substructure — an optimal solution can be built from optimal solutions to its sub-problems.
• Overlapping sub-problems — the same sub-problems are solved multiple times; caching eliminates redundant work.

Two Complementary Approaches

• Top-down (memoisation) — recursive with a cache; natural to write, but carries call-stack overhead.
• Bottom-up (tabulation) — iterative table filled in dependency order; avoids recursion and is often faster in practice.

Difference from Divide & Conquer

Divide & Conquer splits into independent sub-problems and solves each exactly once. DP splits into overlapping sub-problems and stores results to avoid recomputation.

Classes in This Package

• Change — minimum-coins coin-change (bottom-up DP)
• Combinations — combinatorial counting via Pascal's triangle
• Fibonacci — Fibonacci with memoisation and tabulation
• Knapsack01 — 0/1 knapsack problem
• RiverTravel — minimum-cost river crossing

Classes

Class	Description
Change	Coin Change Problem — Dynamic Programming solution.
Combinations	DYNAMIC PROGRAMMING PROBLEM: MATHEMATICAL COMBINATIONS n x k The recursive algorithm that calculates Combinations has exponential complexity and repeats calculations already performed.
Fibonacci	DYNAMIC PROGRAMMING: CALCULATE THE FIBONACCI NUMBER OF ORDER n Fibonacci Series = 0,1,1,2,3,5,8,13,21,34,55,89,... e.g. the 0 is when n=0 and the 89 is when n=11
Knapsack01	0/1 Knapsack Problem - Dynamic Programming Solution.
RiverTravel	DYNAMIC PROGRAMMING PROBLEM: CHEAPER TRAVEL ON THE RIVER It consists on finding the minimum cost for each pair of points