ElectroYou

Ciao a tutti! Scusate se per caso ho sbagliato sezione. Sto cercando di risolvere il seguente esercizio: consiste in poche parole nel cercar di trovare per una matrice quadrata A di dimensioni NxN contenente in ogni cella il peso corrispondente - numero intero, la sequenza di peso minimo che riesca a portarmi dalla prima cella A[1,1] alla cella desiderata A[j,i] in tempo O(N^2) spostandomi solo verso il basso o verso destra (quindi da una cella all'altra posso spostarmi alla cella adiacente a destra, oppure a quella adiacente giù e non verso le altre).
Io ho provato a farlo creando quindi una matrice nuova che in ogni cella la sua distanza da A[1,1] facendo questo ragionamento:
1. la prima riga ha celle alle quali si può arrivare solo da sinistra e la prima colonna solo da sopra quindi basta ogni volta sommare a loro il contenuto iterativamente di quelle precedenti sulla stessa riga o colonna a seconda.
2. le altre celle avranno iterativamente minima distanza contenuta nelle celle . Così si arriva a qualcosa del genere, per esempio:


Dopo per la cella A[j,i] che mi interessa basta tornare sulle orme come nell'immagine prendendo ogni volta il contenuto minimo... Insomma secondo me è giusto e pare che sia O(N^2). Per chi conosce l'algoritmo di Dijkstra il ragionamento che ho fatto credo che sia banale... non so se ho fatto però quello che vuole l'esercizio, perché non capisco la domanda:

Si enunci e si dimostri una proprietà di sottostruttura ottima per
il problema e si derivi una ricorrenza dalla proprietà enunciata.

Io ho praticamente risposto alla seconda domanda ma questa è la prima, non la capisco sinceramente, qualcuno mi può aiutare per favore?