Home > Uncategorized > Project euler: Problem 15

Project euler: Problem 15


You can find the project euler exact problem here. This problem is particularly interesting because it takes a very long time without any optimization. I started with a simple recursion but obviously not efficient, to my surprise the program did not even finish more than 10 minutes :P. The optimized version using dynamic programming hardly takes any time. Here is the code.

#include<stdio.h>

unsigned long long depth(int len)
{
   unsigned long long dep[len + 1][len + 1];
    dep[0][0] = 0;
    for (int i = 1; i <= len; i++) {
        dep[0][i] = 1;
        dep[i][0] = 1;
    }
    for (int i = 1; i <= len; i++) {
        for(int j = 1; j <= len ; j++) {
            dep[i][j] = dep[i - 1][j] + dep[i][j -1];
        }
    }
    return dep[len][len];
}

int main(void)
{
    int len = 20;
    printf("%llu\n", depth(len));
}

Answer: 137846528820

Time it takes to finish the above challenge.

real 0m0.076s
user 0m0.000s
sys 0m0.078s

Advertisements
Categories: Uncategorized
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: