动态编程spoj证明LISA

2 回答

• 0

  这是我的实现:(它假设查询格式正确）

  class LISASolver:
      def solve(self, query):
          """
          takes a query, a string with numbers and +, *,
          returns a tuple of min, max
          """
          numbers, operators = self.parse_inputs(query)
          n = len(numbers)
          self.numbers = numbers
          self.operators = operators
          self.memo = {}
          out = self.dp(0, len(numbers) - 1)
          return out
  
      def dp(self, i, j):
          if i == j:
              n = self.numbers[i]
              return n, n
  
          if (i, j) in self.memo:
              return self.memo[(i, j)]
  
          curmins = []
          curmaxs = []
          for k in range(i, j):
              o = lambda a, b: (a * b) if self.operators[k] == '*' else (a + b)
              leftmin, leftmax = self.dp(i, k)
              rightmin, rightmax = self.dp(k + 1, j)
              curmins.append(o(leftmin, rightmin))
              curmaxs.append(o(leftmax, rightmax))
          self.memo[(i, j)] = (min(curmins), max(curmaxs))
  
          return self.memo[(i, j)]
  
      def parse_inputs(self, query):
          numbers = []
          operators = []
          current_number = []
  
          for c in query:
              if c.isdigit():
                  current_number.append(c)
              else:
                  numbers.append(
                      int(''.join(current_number))
                  )
                  current_number = []
                  operators.append(c)
  
          numbers.append(
              int(''.join(current_number))
          )
          return numbers, operators
  
  s = LISASolver()
  query = '1+2*3+4*5'
  print(s.solve(query))
  >>> 27, 105
  query = '2*0*3+7+1*0*3'
  print(s.solve(query))
  >>> 0, 42
  

  子问题是从第i个数到第j个数的结果的最佳最小和最小结果 . 通过计算每个子阵列上的结果的最小值和最大值来确保最优性，然后应用递归关系 . 时间复杂度为O（n ^ 3），因为存在O（n ^ 2）个子问题并且每个都需要O（n） .

  编辑：

  说明：

  对于动态编程，确定子问题是什么以及子问题如何与其他子问题相关是至关重要的 . 对于这个问题，例如 n 数字（因此 n - 1 运算符），子问题是：通过组合 i -number和 j -number（包括）之间的数字和运算符，可以获得的最小值/最大值是多少 .

  基本情况是 i = j ，我们只有一个数字，最小值/最大值本身 .

  对于任何 j > i ，此问题的子问题是k范围从 i 到 j - 1 左边部分的最小值和最大值（子问题用 i 和 k 作为两个 endpoints ）和右边部分（子问题用 k + 1 和 j 作为两个） endpoints ） . 对于每个 k 我们基本上做的是将 k -th运算符应用为最后一个运算符，因此我们可以为每个 k 获得的最小值是最小值（ operator ）最小值（最大值类似） . （请注意，运算符是 * 或 + ，它们是单调的，因此我们将最小值组合起来得到最小值和最大值以获得最大值 . 对于更多运算符（例如 - 或 / ）的更通用问题，我们可能需要考虑很多情况但是基本结构应该是相同的） . 因此，复发关系很简单

  minimum(i, j) = min(minimum(i, k) [operator] minimum(k + 1, j) for each k)

  (same for max)

  我们必须只解决每个子问题（总共 O(n^2) ）一次并缓存它（或按人们的说法记忆它），每个子问题都需要一个 O(n) 循环来解决 . 因此时间复杂度为 O(n^3) .

  更深入地了解动态编程将真正帮助您解决所有类似的问题 . 如果您不确定在这样的环境中会发生什么，我建议您阅读一些相关内容 .

  回复于 2024-05-16T21:31:35+08:00
• 1

  这个问题可以归类为记忆分而治之的分而治之的问题 .

  想象一下你的字符串是 s = s1 op1 s2 op2 s3 op3 s4

  现在你可以在每个 op 分区 s

  让我们说你在 op1 分区 s 给你两个字符串：

  左字符串： s1 和

  右字符串： s2 op2 s3 op3 s4 .

  让我们说左字符串可以获得的最小值，最大值是 min1, max1

  对于正确的字符串是： min2, max2 .

  您可能认为 min1 op1 min2 是最小的， max1 op1 max2 是最大的

  但尚未完成 .

  您需要为每个 op 执行此操作并累积 min 和 max 的值 . 为什么？因为 op1 处的分区可能不是最佳的 .

  然后在所有这些分区中选择 min(mins) 和 max(maxs)

  你可以通过在Java中记住结果来递归地实现它，如：

  private static int[] recurse( String input, Map<String, int[]> map ) {
      if ( map.containsKey(input) ) {
          return map.get(input);
      }
  
      int[] ans = null;
      List<Integer> mins = new ArrayList<>();
      List<Integer> maxs = new ArrayList<>();
      for ( int i = 0; i < input.length(); i++ ) {
          if ( !Character.isDigit( input.charAt(i) ) ) {
              String left = input.substring(0, i);
              String right = input.substring(i+1);
  
              int[] leftResult = recurse(left, map);
              int[] rightResult = recurse(right, map);
  
              int leftMin = leftResult[0];
              int leftMax = leftResult[1];
  
              int rightMin = rightResult[0];
              int rightMax = rightResult[1];
  
              switch( input.charAt(i) ) 
              {
              case '+':
                  mins.add( leftMin + rightMin );
                  maxs.add( leftMax + rightMax );
                  break;
              case '*':
                  mins.add( leftMin*rightMin );
                  maxs.add( leftMax*rightMax );
                  break;
              default:
                      break;
              }
          }
      }
  
      if ( mins.isEmpty() || maxs.isEmpty() ) {
          ans = new int[]{Integer.valueOf(input), Integer.valueOf(input)};
      } else {
          ans[0] = Integer.MAX_VALUE;
          ans[1] = Integer.MIN_VALUE;
          for ( int i = 0; i < mins.size(); i++ ) {
              ans[0] = Math.min( ans[0], mins.get(i) );
              ans[1] = Math.max( ans[1], maxs.get(i) );
          }
      }
  
      map.put( input, ans );
      return ans;
  }
  
  private static void getMinMax( String in ) {
      if ( in.isEmpty() ) {
          System.out.println("0 0");
          return;
      }
      int[] ans = recurse(in, new HashMap<String, int[]>() );
      System.out.println(ans[1] + " " + ans[0]);
  
  }
  

  回复于 2024-05-16T21:31:35+08:00