--- a/python/dp.py	Sun Feb 19 15:17:09 2023 +0100
+++ b/python/dp.py	Sun Feb 19 15:58:28 2023 +0100
@@ -118,8 +118,33 @@
         print(f"{s[n]} in S2")
         return s12, s22
 
-def rodcut(L, lengths, prices):
+def rodcut(L, lengths, prices, mem=dict()):
     if L < min(lengths):
+        mem[L] = ([], 0)
+        return [], 0
+    if L in mem:
+        return mem[L]
+    best_l, best_p = [], 0
+    for (l, p) in zip(lengths, prices):
+        if L < l:
+            continue
+        l_, p_ = rodcut(L-l, lengths, prices)
+        if p + p_ > best_p:
+            best_p = p+p_
+            best_l = [l] + l_
+    mem[L] = [best_l, best_p]
+    return best_l, best_p
+
+@cache
+def island_death(N, nstep, i=0, j=0):
+    if i < 0 or j < 0 or i >= N or j >= N:
+        return 1
+    elif nstep <= 0:
         return 0
-    return max(p+rodcut(L-l, lengths, prices) for (l, p) in zip(lengths, prices) if L-l >= 0)
+    else:
+        return 1/4 * (
+                island_death(N, nstep-1, i-1, j) +
+                island_death(N, nstep-1, i+1, j) +
+                island_death(N, nstep-1, i, j-1) +
+                island_death(N, nstep-1, i, j+1))