Minimieren Sie die Sequenz durch geeignete Maßnahmen ‚DP‘ setzen
-
27-09-2019 - |
Frage
eine Folge gegeben, sagen wir, 222 Wir haben zu setzen, um ein ‚+‘ oder ‚*‘ zwischen jedem benachbarten Paar. '*' Hat eine höheren Vorrang vor '+'
Wir müssen o / p die Zeichenfolge, deren Auswertung führt zu minimalen Wert. O / p muss lexikographisch kleinsten, wenn es mehr als einen.
inp: 222
o / p: 2 * 2 + 2
Explaination:
2 + 2 + 2 = 6
2 + 2 * 2 = 6
2 * 2 + 2 = 6
dieser dritten lexikographisch kleinsten ist.
Ich habe mich gefragt, wie eine DP Lösung dafür zu konstruieren.
Lösung
Let DP[N]
der kleinste Wert sein, die wir mit den ersten N
Elemente erhalten. Ich werde eine rekursive Implementierung tun (mit memoization) mit Pseudo-Code:
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;
}
Nennen Sie es mit solve(0);
Sie können ganz einfach die Lösung danach rekonstruieren. Ich habe es nicht getestet und vielleicht habe ich einen Vorteil Fall in der Pseudo-Code verpasst, aber es sollten Sie den richtigen Weg geben.
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 Sorry für die vielen Änderungen.