Collegamento problema - link
Devi trovare il percorso con il peso massimo, dalla cella in alto a sinistra alla cella in basso a destra. Potrebbe essere stato risolto con un semplice approccio di programmazione dinamica, se non fosse stato per la condizione speciale - al massimo una mossa è consentita sia a sinistra che in alto. Come posso ora affrontare il problema con questo caso speciale?
Inoltre, sto cercando un approccio efficiente nel tempo.
Grazie!
È ancora fattibile con il caso speciale, ma è necessario aggiungere una terza dimensione logica al DP, indicizzata da una variabile booleana. Questa nuova dimensione distingue tra i punteggi prima della mossa speciale (quando l'indice è false ) e i punteggi dopo la mossa speciale (quando l'indice è true ). Le altre due dimensioni rimangono% della grigliarows e columns .
Quando calcoli il punteggio migliore per una cella a [r][c] , devi calcolare due valori:
false . Questo risultato viene calcolato in base solo ad altri valori della dimensione in cui l'indice è false , guardando le celle a sinistra e in alto da [r][c]
true . Questo risultato viene calcolato in base ai valori di entrambi gli indici: si considerano gli elementi a sinistra e in alto dove l'indice è true , e anche gli elementi a sinistra, a destra, in alto o in basso da [r][c] . Il secondo set di valori (indice == true ) deve essere calcolato dopo aver calcolato l'intero set dei primi elementi. In altre parole, risolvi il problema senza alcuna mossa speciale, quindi usa la tabella per quella soluzione per creare una tabella espansa per la soluzione che consente mosse speciali.
Leggi altre domande sui tag algorithms dynamic-programming