通过把适当的操作“DP”最小化序列

Question

给定的序列，比方说， 222 我们必须把“+”或“*”每个相邻对之间。 '*' 有超过 '+'

更高的优先级

我们必须O / P，其评价导致最小值的字符串。 如果有一个以上的O / p必须按字典顺序最小。

INP：222

O / P：2 * 2 + 2

阐释：

2 + 2 + 2 = 6

2 + 2 * 2 = 6

2×2 + 2 = 6

这个第三的

按字典顺序最小。

我想知道如何构造用于此一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);

P.S很抱歉的许多修改。