Advertisement
gelita

lattice paths

Feb 12th, 2020
232
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5 1.21 KB | None | 0 0
  1. input: int m, int n->  integers of a lattice where m = height and n = width of lattice,
  2. output: number or ways/paths to get from 0,0 to bottom right
  3. example: input: 2,3
  4.         output :10
  5.   (2 x 3 lattice of squares)
  6.    *            0  __1 _2 __3
  7.    *            1 |__ |__|__|
  8.    *            2 |__ |__|__|  
  9.  
  10.  
  11.  
  12. import java.io.*;
  13.  
  14. class MyCode {
  15.     public static void main (String[] args) {
  16.     int m = 10;
  17.     int n = 10;
  18.     //where m = height and n = width
  19.         System.out.println(latticePaths(m,n));
  20.     }
  21.      
  22.     public static int latticePaths(int m, int n) {
  23.         //approach going from input to 0,0
  24.         //if input is 0,0 -> return 1
  25.         if(n == 0 && m == 0){
  26.           return 1;
  27.         }
  28.         //check to see that neither n /m are out of bounds
  29.         //if either is out of bounds then return 0
  30.         //as there is no way to get to -1 in any case
  31.         if(n == -1 || m == -1){
  32.           return 0;
  33.         }
  34.         //decrement m (go upwards)
  35.         int recurseUp = latticePaths(m-1, n);
  36.         //decrement n (go to the left)
  37.         int recurseLeft = latticePaths(m, n-1);
  38.         //get sum of both recursions and return
  39.         return recurseUp + recurseLeft;
  40.     }
  41.  
  42. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement