Matrix Chain Multiplication - parentesizzazione ottima

Moltiplicare una catena di matrici rettangolari può costare molto o poco a seconda dell'ordine in cui si eseguono i prodotti, anche se il risultato è sempre lo stesso: il prodotto è associativo (Operazioni tra matriciLe matrici m×n formano uno spazio vettoriale (somma e prodotto per scalare elemento per elemento); il prodotto righe per colonne corrisponde alla composizione di funzioni lineari, è associativo ma non commutativo; la trasposta scambia righe e colonne e (AB)^T = B^T A^T.Operazioni tra matrici →). Scegliere l'ordine migliore è un problema di ottimizzazione risolto con la programmazione dinamica (Programmazione dinamica - Fibonacci, memoizzazione e schema del paradigmala programmazione dinamica (DP) evolve il divide and conquer: invece di risolvere di nuovo le stesse sottoistanze, le salva in una tabella. Fibonacci ricorsivo costa F_n - 1 addizioni (esponenziale), quello con tabella n - 1. Tre condizioni: sottostruttura, sottoistanze ripetute, spazio dei sottoproblemi ristretto. Bottom-up o memoizzazione (ricorsione + tabella globale). Per i problemi di ottimizzazione lo schema è: sottostruttura ottima, ricorrenza sui costi, informazione addizionale, calcolo della tabella, ricostruzione.Programmazione dinamica - Fibonacci, memoizzazione e schema del paradigma →).

Il problema

Due matrici $A \in \mathbb{C}^{p \times q}$ e $B \in \mathbb{C}^{q \times r}$ sono compatibili (il numero di colonne di $A$ è il numero di righe di $B$) e il prodotto righe per colonne è $C = AB \in \mathbb{C}^{p \times r}$, con $c_{ij} = \sum_{k=1}^{q} a_{ik} b_{kj}$.

RECT_MAT(A, B)
  p <- rows(A); q <- columns(A); r <- columns(B)
  for i <- 1 to p do
    for j <- 1 to r do
      c_ij <- a_i1 * b_1j
      for k <- 2 to q do c_ij <- c_ij + a_ik * b_kj
  return C

Esegue esattamente $p \cdot q \cdot r$ prodotti tra scalari e $p \cdot r \cdot (q - 1)$ somme; come nelle dispense si contano solo i prodotti (vedi anche Prodotto di matrici - algoritmo iterativo e ricorsivo a blocchimodello di costo sulle matrici n x n (operazioni tra scalari, taglia n oppure N = n^2); somma in n^2 operazioni (ottima); prodotto righe per colonne iterativo con costo esatto 2n^3 - n^2; proprietà frattale del prodotto a blocchi dimostrata sugli indici; algoritmo ricorsivo RMUL con T(n) = 8T(n/2) + n^2, Theta(n^3) e soluzione esatta 2n^3 - n^2 per induzione e per srotolamento: fa le stesse operazioni dell'iterativo.Prodotto di matrici - algoritmo iterativo e ricorsivo a blocchi →). Il prodotto è associativo ma non commutativo.

Si vuole il prodotto di una catena $\langle A_1, A_2, \dots, A_n \rangle$ di $n$ matrici rettangolari compatibili (colonne di $A_i$ = righe di $A_{i+1}$). A causa della compatibilità bastano $n + 1$ numeri: il vettore $p = (p_0, p_1, \dots, p_n) \in (\mathbb{N}^+)^{n+1}$, con $A_i \in \mathbb{C}^{p_{i-1} \times p_i}$.

Parentesizzazioni

Ogni ordine di esecuzione è una parentesizzazione completa, e si rappresenta con un albero binario pieno: le foglie sono le matrici, ogni nodo interno è un prodotto (la coppia di parentesi più esterna della sua sottoespressione). Un albero binario pieno con $n$ foglie ha $n - 1$ nodi interni, quindi ogni parentesizzazione esegue esattamente $n - 1$ prodotti tra matrici. Per $n = 3$ ce ne sono due, $((A_1 A_2) A_3)$ e $(A_1 (A_2 A_3))$; per $n = 4$ ce ne sono cinque:

(((A1 A2) A3) A4)    ((A1 A2) (A3 A4))    (A1 (A2 (A3 A4)))    ((A1 (A2 A3)) A4)    (A1 ((A2 A3) A4))

Il numero di prodotti tra scalari invece dipende dalla parentesizzazione, perché dipende dalle dimensioni dei fattori.

Esempio. $A_1 \in \mathbb{C}^{10 \times 100}$, $A_2 \in \mathbb{C}^{100 \times 5}$, $A_3 \in \mathbb{C}^{5 \times 50}$, cioè $p = (10, 100, 5, 50)$.

• $((A_1 A_2) A_3)$: $A_1 A_2$ costa $10 \cdot 100 \cdot 5 = 5000$ e dà una $10 \times 5$; poi $(A_1 A_2) A_3$ costa $10 \cdot 5 \cdot 50 = 2500$. Totale $7500$.
• $(A_1 (A_2 A_3))$: $A_2 A_3$ costa $100 \cdot 5 \cdot 50 = 25\,000$ e dà una $100 \times 50$; poi $A_1 (A_2 A_3)$ costa $10 \cdot 100 \cdot 50 = 50\,000$. Totale $75\,000$.

Già con tre matrici c'è un fattore $10$.

Definizione (MCM). Dato $p \in (\mathbb{N}^+)^{n+1}$, determinare la parentesizzazione della catena associata che richiede il minimo numero di prodotti tra scalari.

L'istanza è solo il vettore $p$: gli elementi delle matrici non servono.

Quante parentesizzazioni?

Sia $P(n)$ il numero di parentesizzazioni di $n$ matrici. L'ultimo prodotto eseguito divide la catena in $\langle A_1, \dots, A_k \rangle$ e $\langle A_{k+1}, \dots, A_n \rangle$, con $1 \le k \le n - 1$; le due sottocatene si parentesizzano indipendentemente, in $P(k)$ e $P(n - k)$ modi:

$$P(n) = \begin{cases} 1 & n = 1 \\ \sum_{k=1}^{n-1} P(k)\, P(n-k) & n > 1 \end{cases}$$

I primi valori sono $1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, \dots$ (numeri di Catalan). La ricorrenza è difficile da risolvere con gli strumenti noti, ma si minora facilmente per induzione.

Teorema. $P(n) \ge \dfrac{2^{n-1}}{n}$ per ogni $n \ge 1$.

Dimostrazione. Base: $P(1) = 1 = 2^0 / 1$ e $P(2) = 1 = 2^1 / 2$. Passo: sia $n \ge 3$ e valga la tesi per i valori minori di $n$. Allora

$$P(n) \ge \sum_{k=1}^{n-1} \frac{2^{k-1}}{k} \cdot \frac{2^{n-k-1}}{n-k} = 2^{n-2} \sum_{k=1}^{n-1} \frac{1}{k(n-k)} \ge 2^{n-2}\left(\frac{1}{n-1} + \frac{1}{n-1}\right) = \frac{2^{n-1}}{n-1} \ge \frac{2^{n-1}}{n}.$$

Nel secondo passaggio la sommatoria è stata minorata con i soli termini $k = 1$ e $k = n - 1$, che sono distinti perché $n \ge 3$ (valgono entrambi $\frac{1}{1 \cdot (n-1)}$). $\square$

Quindi le parentesizzazioni sono esponenziali e la ricerca esaustiva non è praticabile. In realtà $P(n) = \frac{1}{n}\binom{2(n-1)}{n-1}$ (formula dei numeri di Catalan, che si prova per induzione, controllata con Python fino a $n = 14$) e, per l'approssimazione di Stirling, $P(n) = \Theta\!\left(\frac{4^n}{n^{3/2}}\right)$, quadraticamente più grande del limite inferiore dimostrato.

Proprietà di sottostruttura ottima

Una parentesizzazione di $\langle A_1, \dots, A_n \rangle$ contiene parentesizzazioni di sottocatene, quindi lo spazio dei sottoproblemi naturale è l'insieme delle sottocatene non vuote $\langle A_i, \dots, A_j \rangle$ con $1 \le i \le j \le n$: sono $\Theta(n^2)$. Per $i \le j$ si indica con $A_{i..j} = A_i \cdots A_j \in \mathbb{C}^{p_{i-1} \times p_j}$ il prodotto della sottocatena, con $T_{i..j}$ l'albero di una sua parentesizzazione qualsiasi, con $c(T_{i..j})$ il costo (numero di prodotti tra scalari) e con $T^*_{i..j}$ un albero di costo minimo. Si cerca $T^*_{1..n}$.

Casi base: per una sottocatena di una sola matrice $\langle A_i \rangle$ l'unico albero è un nodo, di costo $0$.

Teorema (sottostruttura ottima). Sia $i < j$ e sia $T^*_{i..j}$ un albero ottimo per $\langle A_i, \dots, A_j \rangle$. Allora esiste $k^*$ con $i \le k^* < j$ tale che la radice ha come sottoalberi due alberi ottimi $T^*_{i..k^*}$ e $T^*_{k^*+1..j}$, e $$c(T^*_{i..j}) = c(T^*_{i..k^*}) + c(T^*_{k^*+1..j}) + p_{i-1}\, p_{k^*}\, p_j,$$ dove $k^*$ è un indice che minimizza $c(T^*_{i..k}) + c(T^*_{k+1..j}) + p_{i-1} p_k p_j$ su $i \le k < j$.

Dimostrazione. L'albero ha almeno due foglie, quindi la radice ha due sottoalberi $T_{i..k^*}$ e $T_{k^*+1..j}$, per un certo $i \le k^* < j$: l'ultimo prodotto è $A_{i..k^*} \times A_{k^*+1..j}$, di dimensioni $p_{i-1} \times p_{k^*}$ per $p_{k^*} \times p_j$, che costa $p_{i-1} p_{k^*} p_j$. Il costo totale è quindi $c(T_{i..k^*}) + c(T_{k^*+1..j}) + p_{i-1} p_{k^*} p_j$.

I sottoalberi sono ottimi. Per assurdo, se uno dei due (per esempio $T_{i..k^*}$) non avesse costo minimo, lo si sostituirebbe con un albero ottimo $T^*_{i..k^*}$ della stessa sottocatena: la parentesizzazione risultante è ancora ammissibile (la sottoespressione ha le stesse dimensioni) e costa strettamente meno di $T^*_{i..j}$. Contraddizione. È il cut-and-paste: si taglia una componente, se ne incolla una migliore.

Scelta di $k^*$. Per ogni $k$ con $i \le k < j$, comporre $T^*_{i..k}$ e $T^*_{k+1..j}$ con una nuova radice dà una parentesizzazione ammissibile di costo $c(T^*_{i..k}) + c(T^*_{k+1..j}) + p_{i-1} p_k p_j$. Se $k^*$ non minimizzasse questa quantità, la composizione con il minimo batterebbe $T^*_{i..j}$. $\square$

Il valore $k^*$ è l'unica informazione necessaria a ricostruire l'albero ottimo di $\langle A_i, \dots, A_j \rangle$ dagli alberi ottimi delle sottocatene.

Ricorrenza sui costi

Con $c(i, j) = c(T^*_{i..j})$:

$$c(i, j) = \begin{cases} 0 & i = j \\ \displaystyle\min_{i \le k < j} \big\{\, c(i, k) + c(k+1, j) + p_{i-1}\, p_k\, p_j \,\big\} & 1 \le i < j \le n \end{cases}$$

La soluzione è $c(1, n)$.

L'algoritmo divide and conquer

La ricorrenza si traduce direttamente in codice ricorsivo (chiamata R_MCM(p, 1, n)):

R_MCM(p, i, j)
  if i = j then return 0
  m <- +infinity
  for k <- i to j-1 do
    q <- R_MCM(p, i, k) + R_MCM(p, k+1, j) + p_{i-1} * p_k * p_j
    if q < m then m <- q
  return m

Contando solo i prodotti tra dimensioni (due per ogni $k$: $p_{i-1} p_k$ e il risultato per $p_j$), il costo di una catena di $n$ matrici è

$$T(n) = \begin{cases} 0 & n = 1 \\ \sum_{k=1}^{n-1}\big(T(k) + T(n-k) + 2\big) = 2(n-1) + 2\sum_{k=1}^{n-1} T(k) & n > 1 \end{cases}$$

Minorazione esponenziale. $T(n) \ge 2^n - 2$ per induzione. Base: $T(1) = 0 = 2 - 2$ e $T(2) = 2 = 4 - 2$. Per $n \ge 3$, tenendo solo il termine $k = n - 1$ della sommatoria:

$$T(n) \ge 2(n-1) + 2\,T(n-1) \ge 4 + 2(2^{n-1} - 2) = 2^n,$$

dove si è usato $n - 1 \ge 2$ nel primo addendo. Quindi $T(n) \ge 2^n \ge 2^n - 2$.

Valore esatto: $T(n) = 3^{n-1} - 1$. Per $n \ge 3$ si sottraggono le ricorrenze di $n$ e $n - 1$:

$$T(n) - T(n-1) = 2 + 2\,T(n-1) \quad \Longrightarrow \quad T(n) = 3\,T(n-1) + 2.$$

(La relazione vale anche per $n = 2$: $T(2) = 2 = 3 \cdot 0 + 2$.) Aggiungendo $1$ a entrambi i membri, $T(n) + 1 = 3\,(T(n-1) + 1)$, cioè $T(n) + 1 = 3^{n-1}\,(T(1) + 1) = 3^{n-1}$. Verificato contando le moltiplicazioni di R_MCM per $n \le 8$. Per $n = 4$ sono $26$ e per $n = 10$ sono $19\,682$.

Perché? Per le sottoistanze ripetute. Per $n = 4$ le chiamate a R_MCM(p, i, j) sono in tutto $27$ (cioè $3^{n-1}$), e ogni sottocatena compare più volte:

L'approccio di programmazione dinamica

Si usano due tabelle $m[1..n, 1..n]$ e $s[1..n, 1..n]$, ma solo il triangolo superiore ($i \le j$): $m[i, j]$ contiene $c(i, j)$ e $s[i, j]$ contiene $k^*$ (informazione addizionale). I casi base $m[i, i] = 0$ sono sulla diagonale principale.

Ordine di riempimento. Per calcolare $m[i, j]$ servono $m[i, k]$ (nella stessa riga, a sinistra) e $m[k+1, j]$ (nella stessa colonna, sotto), per $i \le k < j$. La scansione per righe crescenti o per colonne crescenti non funziona: in entrambe $m[k+1, j]$ verrebbe calcolato dopo $m[i, j]$. Ma i valori necessari stanno su diagonali più vicine alla principale. La diagonale $\ell$ contiene le celle con $j - i + 1 = \ell$, cioè le sottocatene di lunghezza $\ell$, e quelle da cui dipende $(i, j)$ sono sottocatene più corte, quindi su diagonali $\ell' < \ell$. Una scansione per diagonali di lunghezza crescente è coerente con le dipendenze. I casi base sono sulla prima diagonale. Sulla diagonale $\ell$ l'indice di riga $i$ va da $1$ a $n - \ell + 1$ e $j = i + \ell - 1$.

MCM(p)
  n <- length(p) - 1
  for i <- 1 to n do m[i, i] <- 0
  for l <- 2 to n do
    for i <- 1 to n - l + 1 do
      j <- i + l - 1
      m[i, j] <- +infinity
      for k <- i to j - 1 do
        q <- m[i, k] + m[k+1, j] + p_{i-1} * p_k * p_j
        if q < m[i, j] then
          m[i, j] <- q
          s[i, j] <- k
  return (m[1, n], s)

Costo (somma esatta). Con costo $2$ per ogni valore di $k$ (i due prodotti tra dimensioni):

$$\begin{aligned} T(n) &= \sum_{\ell=2}^{n} \sum_{i=1}^{n-\ell+1} \sum_{k=i}^{i+\ell-2} 2 = 2\sum_{\ell=2}^{n} \sum_{i=1}^{n-\ell+1} (\ell - 1) = 2\sum_{\ell=2}^{n} (\ell - 1)(n - \ell + 1) \\ &= 2\sum_{\ell'=1}^{n-1} \ell'\,(n - \ell') \qquad (\ell' = \ell - 1) \\ &= 2n \sum_{\ell'=1}^{n-1} \ell' - 2\sum_{\ell'=1}^{n-1} \ell'^2 = 2n \cdot \frac{n(n-1)}{2} - 2\cdot\frac{(n-1)\,n\,(2n-1)}{6} \\ &= n(n-1)\Big(n - \frac{2n-1}{3}\Big) = \frac{n(n-1)(n+1)}{3} = \frac{n^3 - n}{3}, \end{aligned}$$

usando la somma di Gauss e quella dei quadrati (SommatorieIl simbolo di sommatoria, le sue proprietà (linearità, additività, cambio di indice) e le somme notevoli di Gauss e geometrica.Sommatorie →). Quindi $T(n) = \Theta(n^3)$, da confrontare con $3^{n-1} - 1$ del D&C (per $n = 10$: $330$ contro $19\,682$). Controllato contando i prodotti dell'implementazione.

Altre scansioni valide. Per righe dalla riga $n$ alla riga $1$, ciascuna da $m[i, i]$ a $m[i, n]$; oppure per colonne, ciascuna dal basso verso l'alto. Entrambe rispettano il grafico delle dipendenze.

for i <- n downto 1 do                   for j <- 1 to n do
  m[i, i] <- 0                             m[j, j] <- 0
  for j <- i + 1 to n do                   for i <- j - 1 downto 1 do
    (calcolo di m[i, j] come sopra)          (calcolo di m[i, j] come sopra)

Esempio eseguito

$p = (4, 10, 3, 12, 20, 7)$, cioè $n = 5$ matrici: $A_1 \in 4 \times 10$, $A_2 \in 10 \times 3$, $A_3 \in 3 \times 12$, $A_4 \in 12 \times 20$, $A_5 \in 20 \times 7$. Le tabelle (celle dopo la diagonale principale).

Tabella $m[i, j]$:

Tabella $s[i, j]$:

Diagonale per diagonale:

• $\ell = 2$: $m[i, i+1] = p_{i-1} p_i p_{i+1}$: $m[1,2] = 4 \cdot 10 \cdot 3 = 120$; $m[2,3] = 10 \cdot 3 \cdot 12 = 360$; $m[3,4] = 3 \cdot 12 \cdot 20 = 720$; $m[4,5] = 12 \cdot 20 \cdot 7 = 1680$.

• $\ell = 3$, cella $(1, 3)$:

  • $k = 1$: $m[1,1] + m[2,3] + p_0 p_1 p_3 = 0 + 360 + 4 \cdot 10 \cdot 12 = 840$;
  • $k = 2$: $m[1,2] + m[3,3] + p_0 p_2 p_3 = 120 + 0 + 4 \cdot 3 \cdot 12 = 264$.

  Il minimo è $264$ con $k = 2$. Analogamente $m[2,4] = \min\{0 + 720 + 10 \cdot 3 \cdot 20,\ 360 + 0 + 10 \cdot 12 \cdot 20\} = \min\{1320, 2760\} = 1320$ e $m[3,5] = \min\{0 + 1680 + 3 \cdot 12 \cdot 7,\ 720 + 0 + 3 \cdot 20 \cdot 7\} = \min\{1932, 1140\} = 1140$ con $k = 4$.

• $\ell = 4$, cella $(1, 4)$: $k = 1$: $0 + 1320 + 4 \cdot 10 \cdot 20 = 2120$; $k = 2$: $120 + 720 + 4 \cdot 3 \cdot 20 = 1080$; $k = 3$: $264 + 0 + 4 \cdot 12 \cdot 20 = 1224$. Minimo $1080$ con $k = 2$. Per $(2, 5)$: $k = 2$: $0 + 1140 + 10 \cdot 3 \cdot 7 = 1350$; $k = 3$: $360 + 1680 + 10 \cdot 12 \cdot 7 = 2880$; $k = 4$: $1320 + 0 + 10 \cdot 20 \cdot 7 = 2720$; minimo $1350$.

• $\ell = 5$, cella $(1, 5)$: $k = 1$: $0 + 1350 + 4 \cdot 10 \cdot 7 = 1630$; $k = 2$: $120 + 1140 + 4 \cdot 3 \cdot 7 = 1344$; $k = 3$: $264 + 1680 + 4 \cdot 12 \cdot 7 = 2280$; $k = 4$: $1080 + 0 + 4 \cdot 20 \cdot 7 = 1640$. Il minimo è $1344$ con $k = 2$.

Il costo ottimo è $m[1, 5] = 1344$. Ricostruzione: $s[1,5] = 2$ spezza in $\langle A_1, A_2 \rangle$ e $\langle A_3, A_4, A_5 \rangle$; $s[3,5] = 4$ spezza la seconda in $\langle A_3, A_4 \rangle$ e $\langle A_5 \rangle$; $s[3,4] = 3$ e $s[1,2] = 1$ spezzano le coppie. Parentesizzazione: $((A_1 A_2)((A_3 A_4) A_5))$. Controllo del costo: $A_1 A_2$ costa $120$, $A_3 A_4$ costa $720$, $(A_3 A_4) A_5$ costa $3 \cdot 20 \cdot 7 = 420$ e il prodotto finale $4 \cdot 3 \cdot 7 = 84$; totale $120 + 720 + 420 + 84 = 1344$. Dei $14$ ordini possibili questo è l'unico di costo minimo e il peggiore costa $4440$ (calcolato per enumerazione); l'algoritmo è stato confrontato con la forza bruta su $300$ vettori $p$ casuali.

Stampa della parentesizzazione

Un algoritmo ricorsivo che ricalca l'albero:

PRINT_MCM(s, i, j)
  if i = j then
    print("A_i")
    return
  print("(")
  PRINT_MCM(s, i, s[i, j])
  PRINT_MCM(s, s[i, j] + 1, j)
  print(")")

(Nelle dispense manca il return dopo la stampa del caso base: senza di esso il caso $i = j$ proseguirebbe e leggerebbe $s[i,i]$, non definito.) Stampa una parentesi per ogni nodo interno ($2(n-1)$ in tutto) e un carattere per ogni foglia ($n$): $T(n) = n + 2(n - 1) = 3n - 2$ caratteri, ottimo nella dimensione dell'output. In modo analogo, con la tabella $s$ e le matrici, una procedura ricorsiva che chiama RECT_MAT esegue $n - 1$ prodotti tra matrici e in tutto esattamente $m[1, n]$ prodotti tra scalari.

L'approccio memoizzato

Stessa sottostruttura, con la ricorsione e un valore di default per le celle non calcolate. La sentinella è $+\infty$: segnala le celle da calcolare e inizializza correttamente l'accumulo del minimo (i casi base sono già a $0$).

INIT_MCM(p)
  n <- length(p) - 1
  if n = 1 then return 0
  for i <- 1 to n do
    m[i, i] <- 0
    for j <- i + 1 to n do m[i, j] <- +infinity
  return REC_MCM(p, 1, n)

REC_MCM(p, i, j)
  if m[i, j] = +infinity then
    for k <- i to j - 1 do
      q <- REC_MCM(p, i, k) + REC_MCM(p, k+1, j) + p_{i-1} * p_k * p_j
      if q < m[i, j] then m[i, j] <- q
  return m[i, j]

Costo. Ogni sottoistanza non di base $(i, j)$ è un nodo interno una sola volta, con lavoro $2(j - i)$; e da $(1, n)$ si raggiunge ogni coppia $1 \le i < j \le n$ (basta scegliere gli $k$ giusti). Quindi

$$T(n) = \sum_{i=1}^{n-1}\sum_{j=i+1}^{n} 2(j - i) = 2\sum_{d=1}^{n-1} (n - d)\, d = \frac{n^3 - n}{3},$$

(raggruppando per $d = j - i$, che compare $n - d$ volte; stessa somma del bottom-up). Diversamente dalla LCS, la memoizzazione non risparmia mai nulla: tutte le sottoistanze vanno comunque risolte, e la fase top-down non permette di saltarne. Il vantaggio è non dover progettare l'ordine di riempimento per diagonali. Verificato anche questo conteggio con Python per $n < 12$.

Domande d'esame

1. (Risposta numerica.) Sia $p = (1, 9, 10, 4)$ il vettore delle dimensioni di una catena di $3$ matrici. Quanti prodotti tra scalari richiede la parentesizzazione ottima? Svolto in Esercizio - domande di prima parte su programmazione dinamica (simulazioni d'esame): 130, con $((A_1 A_2) A_3)$.
2. (Risposta numerica.) Quante parentesizzazioni distinte ha una catena di $5$ matrici? E quanti prodotti tra scalari (sempre due per $k$) esegue MCM su $n = 10$ matrici? Traccia: $P(5) = 14$ (numero di Catalan); $\frac{n^3 - n}{3} = \frac{990}{3} = 330$.
3. (Quesito aperto.) Perché il D&C su MCM è esponenziale mentre la DP è cubica? Perché la scansione per righe non va bene? Traccia: sottoistanze ripetute (le sottocatene sono $\Theta(n^2)$, ma le chiamate $3^{n-1}$); $m[i, j]$ dipende da $m[k+1, j]$ nelle righe successive, che per righe crescenti non sono pronte; per diagonali sì.