2

给定一个数组 A，假设{5, 5, 4, 3, 7}，使用操作{*, /, + -}并5, 5, 4, 3得到结果为7。如果可能，请打印答案。如果不是，return 0.

Answer : 5 * 5 - 4 / 3 = 7.

我使用递归、蛮力、检查所有案例解决了这个问题。

我的代码：

void check_result(int* arr, int size, char* op, int depth, int result, int val)
{
    if(depth==size)
    {
        if(val==result)
        {
             // call function to print pattern of op[]
        }
        return ;
    }
    else
    {
        op[depth]='+';
        check_result( arr+1, size, op, depth+1, result, val + *arr );

        op[depth]='-';
        check_result( arr+1, size, op, depth+1, result, val - *arr );

        op[depth]='*';
        check_result( arr+1, size, op, depth+1, result, val * (*arr) );

        op[depth]='/';
        if( *arr )
            check_result( arr+1, size, op, depth+1, result, val / (*arr) );
    }
}

你能告诉我这个问题的动态方法吗，因为这需要O(4^n)时间。

4

1 回答 1

1

状态应该是DP[position][currentValue]。这意味着如果您在相应position且拥有currentValue.

boolean rec(int position, int currentValue)
{
   if (position == lastPosition)
   {
      return currentValue == neededResult;
   } 

   if (computed[position][currentValue]) return DP[position][currentValue]; 

   boolean can = false; 
   int nextNumber = numbers[position + 1];

   //Try every operation here and call rec again
   can |= rec(position + 1, currentValue + nextNumber);
   can |= rec(position + 1, currentValue - nextNumber);
   can |= rec(position + 1, currentValue * nextNumber);
   can |= rec(position + 1, currentValue / nextNumber);

   DP[position][currentValue] = can;
   computed[position][currentValue] = true;
   return can;
}

然后，您可以用另一种方法恢复结果：

   void restore(int position, int currentValue)
    {
       if (position == lastPosition) return;

       if (DP[position + 1][currentValue + nextNumber]) 
       { 
          cout << " + ";          
          restore(position + 1, currentValue + nextNumber);
       }
       else
       if (DP[position + 1][currentValue - nextNumber]) 
       { 
          cout << " - ";          
          restore(position + 1, currentValue - nextNumber);
       }
       else
       if (DP[position + 1][currentValue * nextNumber]) 
       { 
          cout << " * ";          
          restore(position + 1, currentValue * nextNumber);
       }
       else
       if (DP[position + 1][currentValue / nextNumber]) 
       { 
          cout << " / ";          
          restore(position + 1, currentValue / nextNumber);
       }
    }

PS 这只是伪代码。可能存在错误和遗漏的极端情况。

于 2012-08-30T11:50:28.880 回答