計算板上最短路徑的數量

Question

我正在嘗試創建一個程序，該程序可以找到nxn板上最短路徑的數量。這應該使用二叉樹遞歸。它需要兩個數字來表示棋盤上某個方塊的位置，並返回指定方塊和左上角之間不同最短路徑的數量。你只能向上，向下，向左或向右移動。

0 1 2 3 4 5 6 7 8 
0 . . . . . . . . . 
1 . . . . . . . . . 
2 . . . . . . . . . 
3 . . . . . . . . . 
4 . . . . . . x . . 
5 . . . . . . . . . 
6 . . . . . . . . . 

在這種情況下，x是在第4行山口6.方案應計數的最短路徑的數量。顯然，如果x在邊上，那麼只有一條最短路徑。

(check-expect (shortest 0 0) 0) 
(check-expect (shortest 0 1) 1) 
(check-expect (shortest 1 0) 1) 
(check-expect (shortest 1 1) 2) 
(check-expect (shortest 1 2) 3) 
(check-expect (shortest 2 1) 3) 
(check-expect (shortest 2 2) 6) 
(check-expect (shortest 2 3) 10) 
(check-expect (shortest 2 7) 36) 
(check-expect (shortest 6 5) 462) 

我相信，我真的很接近，但我有在其他情況下一個問題：

(define (shortest x y) 
    (cond 
    [(= x y 0) 0] 
    [(or (zero? y) (zero? x)) 1] 
    [else (+ 1 (shortest (sub1 x) y) 
       (shortest x (sub1 y)))])) 

我以爲會有的，如果內else語句，但我不知道要測試什麼。

這不應該有任何助手，lambdas，當地人等..和在ISL +。任何幫助都會很棒。

Answer 1

至於如果從

[else (+ 1 (shortest (sub1 x) y) 

改變四號線到

[else (+ (shortest (sub1 x) y) 

功能的要求應該工作，我可以告訴。所以...

(define (shortest x y) 
    (cond 
    [(= x y 0) 0] 
    [(or (zero? y) (zero? x)) 1] 
    [else (+ (shortest (sub1 x) y) 
      (shortest x (sub1 y)))])) 

並且在else中不需要ifs。