This program implements optimized version of dynamic programming approach for all possible path problem

poss_path_optimized.c

int PossiblePaths(int m,int n){

        int Table[n];
        int diagonal_sum =0;
        int i,j;

        for(i=0;i<=n; i++){
                Table[i] =1;
        }

        for(i=1; i<=m; i++ ){
          for(j=1; j<=n; j++){
             diagonal_sum = Table[j-1];
             Table[j] = Table[j] +  Table[j-1] +  diagonal_sum;
          }
        }
        return Table[n];
}