3
Я пытаюсь solve this exercise.Aibohphobia SPOJ
У меня есть решение, как показано ниже, но я получаю сообщение об ошибке Time Limit Exceeded. Я хочу узнать, почему этот код неэффективен, так как я делаю memoization.
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;
}
}
}