Minimize the sequence by placing appropriate "DP" operations
Given a sequence, say 222 We have to put a "+" or "*" between each adjacent pair. '*' takes precedence over '+'
We need an o / p string whose evaluation results in the minimum value. O / p should be lexicographically smallest if there is more.
in: 222
o / p: 2 * 2 + 2
Explaination:
2 + 2 + 2 = 6
2 + 2 * 2 = 6
2 * 2 + 2 = 6
this third is the lexicographically smallest.
I was wondering how to build a DP solution for this.
a source to share
Let be the DP[N]
smallest value that we can get using the first elements N
. I will be doing a recursive implementation (using memoization) with pseudocode:
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;
}
Name it solve(0);
Then you can easily restore the solution. I haven't tested it and maybe I missed the case in the pseudocode, but it should give you the right path.
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);
PS Sorry for the many changes.
a source to share