algorithm - Number of ways from top left to bottom right of an array -

i playing around following problem:

given 2-d array find possible ways can move top left cell [0][0] bottom right cell [n-1][n-1] given can move either downward or rightward?

i defined following:
array such [ [ 1 ] ] there 1 way go start cell destination cell. there.
otherwise total number of ways total number of ways go cell right destination plus 1 (there 1 way go current cell next cell) plus total number of ways go cell bellow destination plus 1 (there 1 way go current cell bellow cell)
array such as:

[     [1, 2]     [3, 4]   ]   

the answer 4 (1->2, 2->4, 1->3, 3->4).
array such as:

[      [1, 2, 3],     [3, 4, 5],    ]   

the answer should 8. 4 comes subarray right + 1 go (1)->(2) plus 1->3 3->4 4->5 total 3.
5 + 3 = 7.
following code seems me correct messing , wrong result.

my $array = [     [1, 2, 3],     [3, 4, 5], ];  sub number_of_ways {     ( $input, $source_row, $source_col, $dest_row, $dest_col ) = @_;      if ( $source_row == $dest_row && $source_col == $dest_col ) {         return 1;     }      if ( $source_row >= scalar @$input) {         return 0;     }     if ( $source_col >= scalar @{$input->[$source_row]} ) {         return 0;     }      $ways_down = number_of_ways($input, $source_row + 1, $source_col, $dest_row, $dest_col);     $ways_right = number_of_ways($input, $source_row, $source_col + 1, $dest_row, $dest_col);      $total = $ways_right + 1 if ( $ways_right );     $total += $ways_down + 1 if ( $ways_down );     return $total; }  print "number of ways: " . number_of_ways($array, 0, 0, 1, 2). "\n";   

this give me 11.
logic wrong?

update:
of @m69 found problem.
in recursion bad idea iteration if can check if going fail. in case, after changing code after comments of @m69 failed because there no distinction between 0 because in subarray 1 element (source , destination same) or outside of array.
following code seems correct.

sub number_of_ways {     ( $input, $source_row, $source_col, $dest_row, $dest_col ) = @_;      if ( $source_row == $dest_row && $source_col == $dest_col ) {         return 0;     }      $total = 0;     if ( $source_row < @$input - 1) {         $ways_down = number_of_ways($input, $source_row + 1, $source_col, $dest_row, $dest_col);         $total += $ways_down + 1;     }     if ( $source_col < @{$input->[$source_row]} - 1 ) {         $ways_right = number_of_ways($input, $source_row, $source_col + 1, $dest_row, $dest_col);          $total += $ways_right + 1;     }      return $total; }  print "number of ways: " . number_of_ways($array, 0, 0, 1, 2). "\n"; 

your algorithm uses recursion:

0   1   2       0---1   2       0             =               +   | 3   4   5           4   5       3   4   5 

which goes on to:

1   2       1---2       1                   =           +   |       , 4   5           5       4   5         3   4   5   =   3---4   5 

and then:

2       2     =   |   ,                       , 5       5         4   5   =   4---5         4   5   =   4---5 

and finally:

5   ,   5   ,   5 

in itself, useful way of recursing in 3x2 grid, way add steps problematic; e.g. after receiving 4 result of recursion 2x2 grid [[1,2][4,5]], add 1 because takes 1 step go position 0 2x2 grid. however, there 2 paths through 2x2 grid, should add 1 step twice. knowing how many paths there through 2x2 grid requires calculating taxicab distance through it, , dividing number of steps distance. you'll see results in lot of unnecessary calculations, because number of steps in each complete path same. it's easier find number of paths, , multiply them number of steps per path.

you can use recursion have find number of paths; breakdown steps of recursion above you'll see end 1x1 grid [5] 3 times. because there 3 paths lead position 5. if count how many times recurse 1x1 grid), know number of paths. know number of steps can multiply (width - 1) + (height - 1) number of steps in each path.

the disadvantage of incrementing variable outside scope of recursion cannot turn dynamic programming solution, because have go through every recursion end, count how many times bottom-right corner. it's better pass results recursion chain.

if return 1 when input 1x1 grid, , sum of right , down result in larger grid (without adding it), gives total number of paths. can memoize results storing 2x1 , 1x2 grid return 1, 2x2 grid returns 2, 3x2 , 2x3 grid returns 3, 3x3 grid returns 6, , use these stored values instead of recursing on grids same size again.

you'll see number of paths through size grid given table:

1  1  1  1  1 ... 1  2  3  4  5 1  3  6 10 15 1  4 10 20 35 1  5 15 35 70 

where each value sum of values above , left of it, points simple non-recursive way calculate number of paths (or steps) through size grid.

---

this code snippet in javascript uses recursion method code count number of paths, , calculates total number of steps:

function count_paths(grid, x, y) {      x = x || 0; y = y || 0;      var height = grid.length - y;      var width = grid[0].length - x;      if (width == 0 || height == 0) return 0;      if (width == 1 && height == 1) return 1;      return count_paths(grid, x + 1, y) + count_paths(grid, x, y + 1);  }    var grid = [[0,1,2,3],[4,5,6,7],[8,9,10,11],[12,13,14,15]];  var paths = count_paths(grid);  var steps = paths * (grid.length - 1 + grid[0].length - 1);  document.write("paths: " + paths + "<br>steps: " + steps);

to integrate calculation of total number of steps recursion, you'd have return number of paths , number of steps, can multiply step takes go right or down number of paths that step leads to:

function count_steps(grid, x, y) {      x = x || 0; y = y || 0;      var height = grid.length - y;      var width = grid[0].length - x;      if (width == 0 || height == 0) return {paths: 0, steps: 0};      if (width == 1 && height == 1) return {paths: 1, steps: 0};      var right = count_steps(grid, x + 1, y);      var down = count_steps(grid, x, y + 1);      var paths = right.paths + down.paths;      var steps = right.steps + down.steps + paths;      return {paths: paths, steps: steps};  }    var grid = [[0,1,2,3],[4,5,6,7],[8,9,10,11],[12,13,14,15]];  var count = count_steps(grid);  document.write("paths: " + count.paths + "<br>steps: " + count.steps);