Advertisement
gelita

unique paths lattice with memoization

Feb 15th, 2020
241
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5 0.58 KB | None | 0 0
  1. public int uniquePaths(int m, int n) {
  2.   if (m == 0 || n == 0) {
  3.     throw new IllegalArgumentException("m or n can't be 0");
  4.   }
  5.   int[][] mem = new int[m][n];
  6.   for (int i = 0; i < m; ++i) { // init
  7.     for (int j = 0; j < n; ++j) {
  8.       mem[i][j] = -1;
  9.     }
  10.   }
  11.   return numPaths(m - 1, n - 1, mem);
  12. }
  13.  
  14. private int numPaths(int i, int j, int[][] mem) {
  15.   if (i == 0 || j == 0) {
  16.     return 1;
  17.   }
  18.   if (mem[i - 1][j] == -1) mem[i - 1][j] = numPaths(i - 1, j, mem);
  19.   if (mem[i][j - 1] == -1) mem[i][j - 1] = numPaths(i, j - 1, mem);
  20.   return mem[i - 1][j] + mem[i][j - 1];
  21. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement