Algorithms and Me: Dynamic programming : Count all possible paths in maze

Given a maze, find count of all paths to reach at right most bottom cell from leftmost top cell.

You can move right, down and diagonally and not left.

If (i == m && j ==n) return 1

Recursion formulation would be

PossiblePaths(i,j,m,n) = PossiblePaths(i+1,j, m,n) // Move down

                        + PossiblePaths(i, j+1, m,n) // Move right

                        + PossiblePaths(i+1, j+1,m,n); // Move diagonally

Table(i,j) = Table(i-1,j) + Table(i,j-1)+ table(i-1,j-1)

int PossiblePaths(int m,int n){

  int Table[m][n];

  int i,j;

  for(i=0;i<=m; i++){

      Table[i][0] =1;

  }

  for(i=0;i<=n; i++){

      Table[0][i] =1;

  }

  for(i=1; i<=m; i++ ){

     for(j=1; j<=n; j++){

         Table[i][j] = Table[i-1][j] +  Table[i][j-1] +  Table[i-1][j-1];

     }

  }

  return Table[m][n];

}

Space optimized version ==> code looks suspicious

Read full article from Algorithms and Me: Dynamic programming : Count all possible paths in maze