Ich suche nach einer effizienten Polynomzeitlösung für das folgende Problem:

Implementieren Sie einen rekursiven Funktionsknoten x y zur Berechnung der (x, y) -ten Zahl in einem als definierten Zahlendreieck

g(x,y) = 0 if |x| > y
       = 1 if (x,y) = (0,0)
       = sum of all incoming paths otherwise

Die Summe aller ankommenden Pfade zu einem Knoten ist definiert als die Summe der Werte aller möglichen Pfade vom Wurzelknoten (x, y) = (0, 0) zum betrachteten Knoten, wobei an jedem Knoten (x, y) ) Ein Pfad kann entweder diagonal nach unten und links (x - 1, y + 1), gerade nach unten (x, y + 1) oder diagonal nach unten und rechts (x + 1, y + 1) verlaufen. Der Wert eines Pfads zu einem Knoten ist definiert als die Summe aller Knoten entlang dieses Pfads bis zum betreffenden Knoten, jedoch ohne diesen.

Die ersten paar Einträge im Nummerndreieck sind in der Tabelle angegeben:

\  x  -3  -2  -1  0  1  2  3 
 \  
y \ _________________________
   |
0  |   0   0   0  1  0  0  0
   |
1  |   0   0   1  1  1  0  0
   |
2  |   0   2   4  6  4  2  0
   |
3  |   4   16  40 48 40 16 4

Ich versuche zuerst eine naive Lösung zu finden. Ich habe Folgendes:

node x y | y < 0                = error "number cannot be negative"
         | (abs x) > y          = 0
         | (x == 0) && (y == 0) = 1
         | otherwise            = node (x+1) (y-1) + node x (y-1) + node (x-1) (y-1)

Wann immer ich das starte bekomme ich:

"* Ausnahme: Stapelüberlauf "?