## Wednesday, 29 April 2009

### PROJECT EULER #76

Link to Project Euler problem 76

It is possible to write five as a sum in exactly six different ways:

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

How many different ways can one hundred be written as a sum of at least two positive integers?

Here we go...yet more virgin territory for me, but isn't that the point?
Partitions....the clue is to store values somewhere, so we do it in a 2-D grid.

`using System;namespace ProjectEuler{    class Program    {        static void Main()        {            //Problem 76            DateTime start = DateTime.Now;            int n = 100;            int[,] a = new int[n + 1, n + 1];            for (int i = 0; i < n + 1; i++)            {                a[i, 0] = 0;                a[0, i] = 1;            }            for (int i = 1; i < n + 1; i++)            {                a[i, 1] = 1;                for (int j = 2; j < n + 1; j++)                {                    int k = i - j;                    if (k < 0)                        a[i, j] = a[i, j - 1];                    else                        a[i, j] = a[i, j - 1] + a[k, j];                }            }            Console.WriteLine(a[n, n - 1]);            TimeSpan time = DateTime.Now - start;            Console.WriteLine("This took {0}", time);            Console.ReadKey();        }    }}`