algorithm - 適切な操作「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

この 3 番目の は、辞書編集的に最小です。

このための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 何度も編集してすみません。