Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created September 13, 2017 06:35
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/7adb0355c85aac41c23fe15fbbb775eb to your computer and use it in GitHub Desktop.
Save jianminchen/7adb0355c85aac41c23fe15fbbb775eb to your computer and use it in GitHub Desktop.
catalan number practice - first writing has a bug (index out of range, negative index value), the line 45 is added to solve the index out of range error
using System;
class Solution
{
public static int NumOfPathsToDest(int n)
{
// your code goes here
if(n < 0)
{
return -1;
}
if(n == 0)
{
return 1;
}
// n > 0
int Size = n ;
var path = new int[Size][];
for(int row = 0; row < Size; row++)
{
path[row] = new int[Size]; // 4
}
for(int row = 0; row < Size; row++)
{
for(int col = 0; col < Size; col++) // not col <= row, 5, 1
{
var isZero = row == 0;
if(isZero)
{
path[0][col] = 1;
}
var blackArea = row > col;
if(blackArea)
{
path[row][col] = 0;
}
else
{
// row - 1 >= 0, col - 1 >= 0
var checking = (row - 1) >= 0 && (col - 1) >= 0;
if(checking)
{
path[row][col] = path[row - 1][col] + path[row][col - 1]; // col - 1 >= 0, row - 1 >= 0
}
}
}
}
return path[n - 1][n - 1];
}
static void Main(string[] args)
{
Console.WriteLine(NumOfPathsToDest(4));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment