我解决了这个 challenge最初使用蛮力并被接受。我试图利用带有内存的动态编程来降低 O(2^n) 的时间复杂度。
使用内存的动态编程比蛮力方法花费的时间更长，我收到了超出时间限制的错误消息。
蛮力方法代码。
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<int, Dictionary<int, int>> dp;
private int numberCalled = 0;
public int doFindSum(ref int[] nums, int index, int current, int target)
{
numberCalled++;
Dictionary<int, int> temp;
if (dp.TryGetValue(index + 1, out temp))
{
int value;
if (temp.TryGetValue(current, out value))
{
return value;
}
}
if (index + 1 == nums.Length)
{
if (current == target)
{
if (!dp.ContainsKey(index + 1))
{
dp.Add(index + 1, new Dictionary<int, int>() { { current, 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(index + 1)) && (add + minus) > 0)
{
dp.Add(index + 1, new Dictionary<int, int>() { { current, add + minus } });
}
return add + minus;
}
public int FindTargetSumWays(int[] nums, int S)
{
numberCalled = 0;
dp = new Dictionary<int, Dictionary<int, int>>(); // index , sum - count
var answer = doFindSum(ref nums, -1, 0, S);
Console.WriteLine("Nums Called = {0}", numberCalled);
return answer;
}
}
驱动代码的代码衡量了每种方法所花费的时间
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 }
};
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);
}
#endregion
Console.ReadLine();
}
这个的输出是
Nums Called = 1023
Brute Force answer => 256, time => 1
Nums Called = 19
DP with memo answer => 256, time => 1
Nums Called = 2097151
Brute Force answer => 6692, time => 29
Nums Called = 2052849
DP with memo answer => 6692, time => 187
Nums Called = 2097151
Brute Force answer => 5756, time => 28
Nums Called = 2036819
DP with memo answer => 5756, time => 176
我不确定为什么动态方法的时间更多，即使调用 doFindSum 方法的次数对于这种方法来说更少。
最佳答案
难怪你的蛮力会被接受，因为在最坏的情况下它会是 O(2^SizeOfArray)。
在我们的例子中是 2^20 的顺序，即大约。 1e6 操作的顺序，20 是问题中提到的输入数组大小的上限。如果这个值很高，它可能会超时，这与我们将看到的 DP 解决方案不同。
对于 DP 解决方案，我们的递归关系如下:
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 Knapsack 问题一样在空间上优化这个问题，因为这个问题完全只依赖于之前的状态。
运行时复杂度为 O(2*SizeOfArray*MaxPossibleSum)，在我们的例子中为 O(2*20*1000)，这绝对低于暴力解决方案。优化代码的空间复杂度将为 O(MaxSum)。
现在关于您的代码问题:
在动态规划中，解决一个大问题应该解决许多小问题，这些小问题只会被解决一次并被多次重复使用。它叫做overlapping sub-problems属性(property)。在这种情况下，您的代码似乎没有利用它。为什么？因为在我们的问题中，DP 状态由两个变量“index”和“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#。我之前没有任何经验。
关于algorithm - 具有记忆化的动态编程比蛮力方法花费的时间更长，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/43599159/