# Project Euler Problem 76

Frankly, I snooped the approach for solving Project Euler Problem 76 at the times of working on solution to Project Euler Problem 31. I wasn’t very happy with my solution and was looking thru Project Euler Problem 31 Forum for alternative approaches. There I spotted one that is perfectly applicable to solving of the current problem, also belonging to Integer Partition type. It is based on dynamic programming approach: if we try partitioning number **n** with an addendum **x**, then how many ways exist to partition number **n – x** with addendums that are less, or equal, than **x**? This approach allows finding the answer for this question for addendum **i** based on answer for the same question for smaller addendums. After growing our addendums from **1** to **99** we eventually get to the number of partitionings for **n = 100**:

let problem076() = let n = 100 let partitions = Array.zeroCreate (n + 1) partitions.[0] <- 1 for addendum in 1..n - 1 do for i in addendum..n do partitions.[i] <- partitions.[i] + partitions.[i - addendum] partitions.[n]

## Trackbacks & Pingbacks