programmazione dinamica

[evilspirit2000]

Non riesco a risolvere alcuni problemi. ve ne descrivo uno:
ho in input una matrice binaria quadrata nxn. Devo ricercare in questa matrice la più grande sottomatrice quadrata formata da soli 0.
l'algoritmo deve essere sviluppato in programmazione dinamica utilizzando metodo top-down.

input soluzione
0001 1110
0000 1222
0100 1222
0010 1222

la mia idea è la seguente:
utilizzo una matrice T nxn nella quale T[i,j] = alla dimensione della più grande sottomatrice di 0 che posso ottenere se la matrice di imput avesse i righe e j colonne. per dimensione intendo la lunghezza di un lato.
nella cella T[1,n] ci sarà la dimensione della più grande sottomatrice di 0.
il tutto sta nel trovare la ricorsione:

T[i,j]=
1 se input[i,j]=0,
0 se input[i,j]=1
con i=1 or j=1

T[i,j]=1 + min [T[i,j-1], T[i-1,j], T[i-1,j-1]] con input[i,j]=0
T[i,j]=max [T[i,j-1], T[i-1,j]] con input[i,j]=1

tale ricorsione non è giusta. in alcuni casi restituisce la soluzione in altri no. ad esempio con l'input precedente sbaglia, restituendo:

1110
1221
1232
1233

potete darmi una mano per risolverlo?
grazie

[gugoXX]

http://www.hwupgrade.it/forum/showthread.php?t=1799059