The number of paths using "Catalan Numbers" Logic & "Dynamic Programming".


  • 0
    J

    The number of paths with 2n steps on a rectangular grid from bottom left, i.e., (n-1, 0) to top right (0, n-1) that do not cross above the main diagonal.

    alt text

    alt text

    class Solution {
    
       public static int numOfPathsToDest(int n) {
    	   int matrix[][] = new int[n][n];
    	   
    	   for (int i = 0; i < n; i++) {
    	        matrix[0][i] = 1;		        
    	   }
    	   
    	   for (int i = 1; i < n; i++) {
    	     for (int  j = i; j < n; j++) {
    	        matrix[i][j] = matrix[i-1][j] + matrix[i][j-1];
    	      }
    	    }
    	    return matrix[n-1][n-1];
    	 }
    }
    

    Usefull Links:
    https://www.geeksforgeeks.org/applications-of-catalan-numbers/
    https://www.youtube.com/watch?v=2NZF2UKyh0g

    Similar Approach help us to solve below Question:

    1. Number of possible Binary Search Trees with n keys.
    2. Number of expressions containing n pairs of parentheses which are correctly matched.
      For n = 3, possible expressions are ((())), ()(()), ()()(), (())(), (()()).

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.