Explores the classic coin change problem using dynamic programming with array-based solutions. Demonstrates how to build a DP array where each index represents the minimum coins needed for that amount, starting from a base case of zero. Provides complete implementations in both Rust (using mutable vectors) and Haskell (using immutable IntMap), highlighting the differences in handling array mutations between imperative and functional approaches. Explains why greedy algorithms fail for this problem and walks through the logic of looking back in the array based on coin values to find optimal solutions.
Sort: