Minimizzare la sequenza mettendo operazioni appropriate 'DP'
-
27-09-2019 - |
Domanda
Data una sequenza, per esempio, 222 Dobbiamo mettere un '+' o '*' fra ciascuna coppia adiacente. '*' Ha una maggiore precedenza su '+'
Dobbiamo o / p stringa la cui valutazione porta a valore minimo. O / p deve essere lessicografico più piccolo se ci sono più di uno.
INP: 222
o / p: 2 * 2 + 2
Spiegazione:
2 + 2 + 2 = 6
2 + 2 * 2 = 6
2 * 2 + 2 = 6
di questo terzo è lexicographically più piccolo.
Mi chiedevo come costruire una soluzione DP per questo.
Soluzione
Sia DP[N]
essere il valore più piccolo si possono ottenere utilizzando i primi elementi N
. Farò un'implementazione ricorsiva (usando Memoizzazione) con pseudocodice:
int solve(int index)
{
if (index == N)
return 0;
if (DP[index] already computed)
return DP[index];
int result = INFINITELY LARGE NUMBER;
//put a + sign
result = min(result, input[index] + solve(index + 1));
//put consecutive * signs
int cur = input[index];
for (int i = index + 1; i < N; i++)
{
cur *= input[i];
result = min(result, cur + solve(i + 1));
}
return DP[index] = result;
}
Lo chiamano con solve(0);
Si può facilmente ricostruire la soluzione dopo questo. Non ho ancora testato e forse ho perso un caso limite in pseudocodice ma dovrebbe darvi la strada giusta.
string reconstruct(int index)
{
if (index == N)
return "";
string result = "";
//put consecutive * signs
int cur = input[index];
string temp = ToString(input[index]);
for (int i = index + 1; i < N; i++)
{
cur *= input[i];
temp += "*";
if (DP[index] == cur + DP[i + 1])
result = temp + reconstruct(i + 1);
}
//put a + sign
if (result == "")
result = ToString(input[index]) + "+" + reconstruct(index + 1);
return result;
}
string result = reconstruct(0);
P.S Ci dispiace per i tanti modifiche.