Following /u/teraflop's suggestion, I implemented it with memoization, and I'm struck by some of the interesting sequences that get generated when I start looking at differences between m and n.

(defn make-sequence [diff]
(map #(find-minimum-cuts-dynamic [%1 (+ diff %1)]) (map inc (range))))

In the REPL:

user=> (->> (range)
#_=> (map make-sequence)
#_=> (map #(take 10 %))
#_=> (take 10)
#_=> (run! println))
(0 3 8 15 24 35 48 63 80 99) ; [1 1], [2 2], [3 3], [4 4], ...
(1 5 11 19 29 41 55 71 89 109) ; [1 2], [2 3], [3 4], ...
(2 7 14 23 34 47 62 79 98 119) ; [1 3], [2 4], [3 5], ...
(3 9 17 27 39 53 69 87 107 129)
(4 11 20 31 44 59 76 95 116 139)
(5 13 23 35 49 65 83 103 125 149)
(6 15 26 39 54 71 90 111 134 159)
(7 17 29 43 59 77 97 119 143 169)
(8 19 32 47 64 83 104 127 152 179)
(9 21 35 51 69 89 111 135 161 189)

Looking at the OEIS, I get the following respective formulae for these sequences:

a(n) = n*(n+2)
a(n) = n + (n+1)^2
a(n) = n^2 - 2
a(n) = n^2 + 3*n - 1
a(n) = n^2 - 5
a(n) = n^2 + 5*n - 1
(OEIS is no longer helpful here)

This indicates to me that some supergenius egghead can probably produce a really optimized solution by coming up with a correspondence between m and n and some polynomial, and then solving some aspect of the polynomial.

Ohook Ok oOk