Lattice paths: https://projecteuler.net/problem=15

LatticePaths.java

import java.io.*;
import java.util.*;
import java.util.concurrent.*;

import org.junit.*;
import org.junit.runner.*;

public class LatticePaths {
  private final Map<RectangleDimensions, Integer> numberOfPathsMemo = new ConcurrentHashMap<RectangleDimensions, Integer>();
  
  public int numberOfPaths(final int width, final int height) {
    if (width < height) {
      return numberOfPaths(height, width);
    }
    
    if (height == 0) {
      return 1;
    } else if (height == 1) {
      return width + 1;
    } else {
      final RectangleDimensions rectangleDimensions = new RectangleDimensions(width, height);
      
      int pathCount = numberOfPathsMemo.getOrDefault(rectangleDimensions, 0);
      
      if (pathCount == 0) {
        // Tally up for each vertex on the diagonal the number of paths to that vertex times the number of paths from that vertex
        for (int w = width, h = 0; w >= 0 && h <= height; --w, ++h) {
          pathCount += numberOfPaths(w, h) * numberOfPaths(width - w, height - h);
        }
      
        numberOfPathsMemo.put(rectangleDimensions, pathCount);
      }
      
      return pathCount;
    }
  }
  
  @Test
  public void test2By2() {
    Assert.assertEquals(6, numberOfPaths(2, 2));
  }
  
  public static void main(String[] args) {
    JUnitCore.main("LatticePaths");
  }
}