Project Euler Problem 15: Lattice paths

Problem

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20×20 grid?

Solution

The lesson learnt is avoid recursive as it hurts your performance badly!

 private static final int NUMBER = 20;  
      private static final long[][] grid = new long[NUMBER+1][NUMBER+1];  
      public static void main(String[] args) {  
           grid[0][0] = 0;  
           for (int i=1; i <= NUMBER; i++){  
                grid[i][0] = 1;  
                grid[0][i] = 1;  
           }  
           for (int i=1; i <= NUMBER; i++){  
                for (int j=1; j <=i; j++){  
                     grid[i][j] = grid[j][i] = grid[j-1][i] + grid[j][i-1];  
                }  
           }  
           System.out.println(grid[NUMBER][NUMBER]);  
      }