algorithm - 通过放置适当的操作'DP'来最小化序列

Question

给定一个序列，比如 222 我们必须在每个相邻对之间放置一个“+”或“*”。'*' 优先于 '+'

我们必须 o/p 其评估导致最小值的字符串。如果有多个，O/p 必须是字典最小的。

输入：222

o/p：2*2+2

解释：

2+2+2=6

2+2*2=6

2*2+2=6

这个 3rd 在字典上是最小的。

我想知道如何为此构建一个 DP 解决方案。

Answer 1

让我们可以使用第一个元素DP[N]获得的最小值。N我将使用伪代码进行递归实现（使用记忆化）：

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;
}

调用它solve(0);

在此之后，您可以轻松地重建解决方案。我还没有测试过它，也许我错过了伪代码中的一个边缘案例，但它应该给你正确的轨道。

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 很抱歉进行了许多编辑。