动态编程与记忆耗时比蛮力方法更长

2 回答

• 1

  难怪你的暴力被接受了，因为在最坏的情况下它会是O（2 ^ SizeOfArray） .

  ---

  在我们的情况下，顺序为2 ^ 20，即约 . 1e6操作的顺序，20是输入中数组大小的上限，如问题中所述 . 如果这个很高，它可能会像DP解决方案那样超时，我们将会看到 .

  ---

  Coming to the DP solution our recursive relation would be like:

  for all S in range(-MaxSum,MaxSum) and i in range(1,SizeOfArray)
       count[i][S] = count[ i-1 ][ S-arr[i] ] + count[ i-1 ][ S+arr[i] ]
  

  为简单起见，只关注这一部分：

  count[i][S] = count[ i-1 ][ S-arr[i] ] + count[ i-1 ][ S+arr[i] ]
  

  它只取决于以前的状态 . 所以你可以在0-1背包问题中在空间中进行优化，因为问题完全取决于之前的状态 .

  运行时复杂度将是 O(2*SizeOfArray*MaxPossibleSum) ，在我们的例子中是O（2 * 20 * 1000），这肯定小于暴力解决方案 . 优化代码的空间复杂度将为 O(MaxSum) .

  Now regarding problem with your code:

  在动态编程中，解决一个大问题应解决许多小问题，这些问题只能解决一次并重复使用多次 . 它被称为overlapping sub-problems属性 . 在这种情况下，您的代码似乎没有利用它 . 为什么？因为在我们的问题中，DP状态由您声明的两个变量“ index " and " current ”组成，但您只是根据索引输入备忘录 . 这是问题所在 . 我在你的代码中做了一些修改 . 现在它的速度比蛮力的速度快 .

  using System;
  using System.Collections.Generic;
  using System.Diagnostics;
  public class Dummy
  {
      private int answer = 0;
      private int numberCalled = 0;
      public bool doFindSum(ref int[] nums, int index, int current, int target)
      {
          numberCalled++;
          if (index + 1 == nums.Length)
          {
              if (current == target)
              {
                  ++answer;
                  return true;
              }
              else
              {
                  return false;
              }
          }
          bool add = doFindSum(ref nums, index + 1, current + nums[index + 1], target);
          bool minus = doFindSum(ref nums, index + 1, current - nums[index + 1], target);
          return add || minus;
      }
      public int FindTargetSumWays(int[] nums, int S)
      {
          numberCalled = 0;
          doFindSum(ref nums, -1, 0, S);
          Console.WriteLine("Nums Called = {0}", numberCalled);
          return answer;
      }
  }
  
  public class DP{
      private Dictionary<Tuple<int,int>,int> dp;
      private int numberCalled = 0;
      private int tp1=0;
      public int doFindSum(ref int[] nums, int index, int current, int target)
      {
          numberCalled++;
          Tuple<int,int> tp=new Tuple<int,int>(index+1,current);
          int value;
          if (dp.TryGetValue(tp, out value))
          {
                  tp1++;
                  return value;
          }
          if (index + 1 == nums.Length)
          {
              if (current == target)
              {
                  if (!dp.ContainsKey(tp))
                  {
                      dp.Add(tp, 1);
                      return 1;
                  }
              }
              return 0;
          }
          int add = doFindSum(ref nums, index + 1, current + nums[index + 1], target);
          int minus = doFindSum(ref nums, index + 1, current - nums[index + 1], target);
          if ((!dp.ContainsKey(tp)))
          {
              dp.Add(tp, add + minus);
          }
  
          return add + minus;
  
  
      }
      public int FindTargetSumWays(int[] nums, int S)
      {
          numberCalled = 0;
          dp = new Dictionary<Tuple<int,int>,int>(); // index , sum - count
          var answer =  doFindSum(ref nums, -1, 0, S);
          Console.WriteLine("Nums Called = {0} tp={1}", numberCalled,tp1);
          return answer;
      }
  }
  
  public class sol{
  public static void Main(string[] args)
          {
  
               var ip = new int[][] { new int [] { 0, 0, 0, 0, 0, 0, 0, 0, 1},
                                  new int [] {6,44,30,25,8,26,34,22,10,18,34,8,0,32,13,48,29,41,16,30},
                                  new int []{7,46,36,49,5,34,25,39,41,38,49,47,17,11,1,41,7,16,23,13,1,1,0,0,1,1,1,1,1,1 }
              };
          var target = new int[] { 1, 12, 3 };
          for (int i = 0; i < target.Length; i++)
          {
              var sw = Stopwatch.StartNew();
              var dummy = new Dummy();
            //  Console.WriteLine("Brute Force  answer => {0},  time => {1}", dummy.FindTargetSumWays(ip[i], target[i]), sw.ElapsedMilliseconds);
              sw.Restart();
              var dp = new DP();
              Console.WriteLine("DP with memo answer => {0},  time => {1}", dp.FindTargetSumWays(ip[i], target[i]), sw.ElapsedMilliseconds);
          }
  
          Console.ReadLine();
      }
  }
  

  我必须说，虽然今天我学到了一点C＃ . 我之前没有任何经验 .

  回复于 2024-04-30T20:23:23+08:00
• 1

  我不太了解你的memoization代码，但对我来说似乎太复杂了 . 您所需要的只是记住一些数量的nums的所有可能总和的可能组合的数量 . 您一次添加一个数字并更新这些总和 . 你从零和的一个可能的组合开始 .

  public int FindTargetSumWays(int[] nums, int S)
  {
      int numberCalled = 0;
  
      int sum = nums.Sum();
      if (Math.Abs(S) > sum) { return 0; }
  
      int[] arr = new int[2 * sum + 1];
      arr[0] = 1;
      int upperBound = 0;
  
      foreach (int num in nums)
      {
          int num2 = 2 * num;
          upperBound += num2;
          for (int i = upperBound; i >= num2; --i)
          {
              arr[i] += arr[i - num2];
              numberCalled++;
          }
      }
  
      Console.WriteLine("Nums Called = {0}", numberCalled);
      return arr[S + sum];
  }
  

  回复于 2024-04-30T20:23:23+08:00