Минимизируйте последовательность, поместив соответствующие операции «DP»

Question

Учитывая последовательность, скажем, 222 Мы должны поставить «+» или «*» между каждой соседней парой. «*» имеет более высокий приоритет над «+»

Мы должны о / п строки, оценка которой приводит к минимальному значению. O / p должно быть лексикографически наименьшим, если их больше одного.

ве: 222

о / п: 2 * 2 + 2

Explaination:

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

P.S Извините за многочисленные правки.