從左上角到一個數組

Question

我是用下面的問題玩耍的右下角方式號碼：

鑑於2 d陣列找到所有我們可以從頂部 左上角單元格移動的可能途徑[0][0]到底部右側單元格[N-1][N-1]因爲我們 只能向下或向右移動？

我定義以下：
對於數組如[ [ 1 ] ]只有1路從開始小區到目的地小區去。我們已經在那裏。
否則它的方式總數是我們從小區到目的地的方式總數加1（從當前小區到下一個小區有1種方式）再加上我們的總數從細胞波紋管到目標加1去（存在從當前小區到去到波紋管單元1點的方式）
所以對於陣列如：

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

答案是4（1-> 2→2→4,1→3→3→4）。
對於數組如：

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

答案應該是8。4來自子陣列向右+ 1去（1） - >（2）加1-> 3 3-> 4 4-> 5共3.
所以5 + 3 = 7.
下面的代碼在我看來是正確的，但我搞砸了一些東西，我得到了錯誤的結果。

my $array = [ 
    [1, 2, 3], 
    [3, 4, 5], 
]; 

sub number_of_ways { 
    my ($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; 
    } 

    my $ways_down = number_of_ways($input, $source_row + 1, $source_col, $dest_row, $dest_col); 
    my $ways_right = number_of_ways($input, $source_row, $source_col + 1, $dest_row, $dest_col); 
    my $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"; 

這給我11
是邏輯錯誤？

更新：
在@ m69的幫助下，我發現了問題。
如果我們已經可以檢查它是否會失敗，那麼在遞歸中進行迭代是一個壞主意。在這種情況下，即使在@ m69的註釋之後更改代碼之後，它仍然失敗，因爲0之間沒有區別，因爲我們位於具有1個元素的子數組中（源和目標相同）或數組外部。
以下代碼似乎是正確的。

sub number_of_ways { 
    my ($input, $source_row, $source_col, $dest_row, $dest_col) = @_; 

    if ($source_row == $dest_row && $source_col == $dest_col) { 
     return 0; 
    } 

    my $total = 0; 
    if ($source_row < @$input - 1) { 
     my $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) { 
     my $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"; 

Answer 1

你的算法使用此遞歸：

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

，然後繼續到：

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

然後：

2  2 
    = | AND      AND 
5  5   4 5 = 4---5   4 5 = 4---5 

最後：

5 AND 5 AND 5 

本身，這是在3x2網格中遞歸的一種有用方式，但是您添加步驟的方式是有問題的;例如在用2×2網格[[1,2] [4,5]]遞歸的結果接收4之後，將1加1，因爲它需要1步從位置0移動到2×2網格。但是，通過2x2網格有兩條路徑，所以您應該添加兩步。通過2×2網格知道有多少路徑需要通過它計算出租車距離，然後將步數除以該距離。您會看到這會導致大量不必要的計算，因爲每個完整路徑中的步數總是相同的。所以找到路徑的數量要容易得多，然後將它們乘以每個路徑的步數。

您可以使用遞歸你必須要找到的路徑的數量;從分解到上面遞歸的步驟，你會看到你最終得到了3次1x1的網格[5]。這是因爲有三條路徑導致位置5.如果您只是計算您使用該1x1網格遞歸的次數），則知道路徑的數量。要知道步數，然後乘以（寬度 - 1）+（高度 - 1），這是每個路徑中的步數。

簡單地遞增遞歸範圍之外的變量的缺點是您不能輕易將其變爲動態編程解決方案，因爲您必須通過每次遞歸到最後來計算您獲得了多少次到右下角。所以最好將結果傳遞迴遞歸鏈。

如果返回1當輸入爲一個1x1的網格，在更大的網格向右和向下的結果（不添加任何東西的話）的總和，這也給您的路徑總數。然後，你可以通過存儲2×1和1×2柵格返回1，2×2網格返回參照圖2，3×2和2×3網格返回3，3×3的網格返回6 memoize的結果，並且使用，而不是遞歸超過網格具有相同的這些存儲的值大小再次。

你會看到，通過任何大小格的路徑的數量由表中給出：

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 

其中每個值是值的上方和它的左側，這也指出總和以簡單的非遞歸方式計算通過任何大小的網格的路徑（或步驟）的數量。

---

在JavaScript這段代碼使用遞歸方法從您的代碼來計算路徑的數量，然後計算總步數：

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);

爲了整合步驟進入遞歸總數的計算，你必須返回的路徑數和步數，這樣就可以乘步需要由路徑的數目t走向右或向下該步驟導致帽子：

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);