Aibohphobia SPOJ

Question

Я пытаюсь решить это упражнение.

У меня есть решение, как показано ниже, но я получаю 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;
        }    
  }
}

Answer 1

Вы запоминаете свои результаты в Dictionary<string, int>, который, по сути, является хэш-таблицей. Это означает, что каждый раз, когда вы хотите получить значение для данного ключа, вы должны вычислить хеш-функцию ключа.

В этом случае, так как тип вашего ключа stringоценка хеш-функции, безусловно, замедляет ваше выполнение. Я предлагаю вам запомнить ваши значения для DP в int[][] matrixПоэтому вы можете получить значения, которые вы хотите гораздо быстрее.

Чтобы достичь этого, вам придется выяснить, как составить карту вашего strings в ints, Вы можете найти краткий учебник о том, как это сделать, здесь: String Hashing для конкурентного программирования, где автор объясняет простые методы хеширования строк.