Log in

tachikoma valentines

Dynamic programming to the rescue

Project Euler, problem 76: “How many different ways can one hundred be written as a sum of at least two positive integers?”

Well, hmm.  There are $\sum_{i=1}^{99}\begin{pmatrix}99\\i\end{pmatrix}$=299-1=633825300114114700748351602687 ways of partitioning 100.  Eliminate duplicates (1+2=2+1) and we’ll have the answer… in a trillion years or so.  That’s not really a good solution.

A better solution would use a better method.  Does f(n,m)=$\left{\begin{matrix}0&,&n<0\\1&,&n=0\\\sum_{i=1}^{m}f(n-i,i)&,&\text{otherwise}\end{matrix}\right.$, g(n)=f(n,n)-1 look usable?  g(n) will take us through a n-depth call stack, forking out into O(2n) different function calls – just like before, the complexity is still too high to fit within Project Euler’s suggested "one-minute" maximum compute time.

p=repeat 1:[[sum[p!!(n-i)!!i|i<-[1..min m n]]|m<-[0..]]|n<-[1..]]
#include <stdio.h>
#define TOP 100
static int ways[TOP];
int main() {
    int i, j;
    for (i = 1; i < TOP; i++) {
        ways[i - 1]++;
        for (j = 0; i + j < TOP; j++)
            ways[j + i] += ways[j];
    printf("%d\n", ways[TOP - 1]);
J, Haskell, and C respectively, all running in under one second.

Both Haskell and C have been memoized manually, while J takes advantage of M., the auto-memoizer.  Now, ain’t that a handy language built-in?