我正在尝试 solve this exercise.
我有一个解决方案,如下所示,但我收到了 Time Limit Exceeded
错误。我想了解为什么这段代码效率低下,因为我正在做内存。
namespace Aibohphobia
{
class Test
{
static Dictionary<string, int> memo = new Dictionary<string, int>();
static int Main(string[] args)
{
string num = Console.ReadLine();
int N = int.Parse(num);
string input = string.Empty;
for (int i = 0; i < N; i++)
{
memo = new Dictionary<string, int>();
input = Console.ReadLine();
int count = new Test().insert(input, 0, input.Length - 1);
Console.WriteLine(count);
}
return 0;
}
int insert(string input, int start, int end)
{
int count = 0;
var key = start + "_" + end;
if (start >= end)
return 0;
if (memo.ContainsKey(key))
return memo[key];
if (input[start] == input[end])
{
count += insert(input, start + 1, end - 1);
}
else
{
int countLeft = 1 + insert(input, start + 1, end);
int countRight = 1 + insert(input, start, end - 1);
count += Math.Min(countLeft, countRight);
}
memo.Add(key, count);
return count;
}
}
}
最佳答案
您正在内存您的结果在 Dictionary<string, int>
中,本质上是一个哈希表。这意味着每次要检索给定键的值时,都必须计算该键的哈希函数。
在这种情况下,因为您的 key 类型是 string
,哈希函数的评估肯定会减慢您的执行速度。我建议您记住您在 int[][] matrix
中对 DP 的值(value)观。 ,因此您可以更快地检索所需的值。
为了实现这一目标,您将了解如何映射您的 strings
至 ints
.您可以在此处找到有关如何执行此操作的简短教程:String Hashing for competitive programming ,其中作者解释了简单的字符串散列技术。
关于c# - 恐惧症SPOJ,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34114848/