Created
August 31, 2017 06:34
-
-
Save jianminchen/cd14a02d6a40481ffbcf462515bdb0d3 to your computer and use it in GitHub Desktop.
Catalan number practice - C# code
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
class Solution | |
{ | |
public static int NumOfPathsToDest(int n) | |
{ | |
// your code goes here | |
if( n < 0) | |
{ | |
return -1; | |
} | |
if( n == 0) | |
{ | |
return 1; | |
} | |
var paths = new int[n, n]; | |
for(int row = 0; row < n; row ++) | |
{ | |
var isFirstRow = row == 0; | |
for(int col = 0; col < n; col ++) | |
{ | |
if(isFirstRow) | |
{ | |
paths[0, col] = 1; // only by going right | |
} | |
else if( row > col) | |
{ | |
paths[row, col] = 0; | |
} | |
else if( row == col) | |
{ | |
paths[row, col] = paths[row - 1, col]; | |
} | |
else if ( row < col) // (4,5) -> (3, 5) go north, (4, 4) -> right | |
{ | |
paths[row, col] = paths[row - 1, col] + paths[row, col - 1]; | |
} | |
} | |
} | |
return paths[n -1, n - 1]; | |
} | |
static void Main(string[] args) | |
{ | |
} | |
} | |
// n = 4, output = 5 | |
//NOT accepted (i >= j: xVal >= yVal) | |
// (1,0) -> (0,0) -> right NPD(1,0) = NPD(0,0) | |
// NPD(n, 0) = NPD(0,0) = 1, n from 0 to 5 | |
// NPD(row, col), col > row , NPD(rol, col) = 0 | |
// NPD(row, row) = NPD( row, row -1 ), row >= 1, on the red line | |
// NPD(row, col), if col < row, then NPD(row, col) = NPD(row -1, col) + NPD(row, col -1) | |
// | |
// int[n,n] -> right | |
// base case -> row = 0 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment