Как это решение является примером динамического программирования?

Question

Лектор задал этот вопрос в классе: [Вопрос]

Последовательность из n целых чисел хранится в массив A [1..n]. Целое число в A является называется большинство, если оно кажется более чем н / 2 раза в А.

Алгоритм O (n) может быть разработан для найти большинство на основе следующее наблюдение: если два разные элементы в оригинале последовательность удаляется, то большинство в исходной последовательности остается большинством в новом последовательность. Используя это наблюдение, или в противном случае напишите программный код найти большинство, если таковое существует, в O (n) время.

, для которого было принято это решение [Раствор]

int findCandidate(int[] a)
{
    int maj_index = 0;
    int count = 1;
    for (int i=1;i<a.length;i++)
    {
        if (a[maj_index] == a[i])
            count++;
        else
            count--;

        if (count == 0)
        {
            maj_index =i;
            count++;
        }
    }
    return a[maj_index];
}

int findMajority(int[] a)
{
    int c = findCandidate(a);
    int count = 0;
    for (int i=0;i<a.length;i++)
        if (a[i] == c) count++;

    if (count > n/2) return c;
    return -1;//just a marker - no majority found
}

Я не вижу, как предоставленное решение является динамическим решением. И я не вижу, как, основываясь на формулировке, он вытащил этот код.

Answer 1

Источник термина динамического программирования пытается описать действительно удивительный способ оптимизации определенных видов решений (использовался динамический, поскольку он звучал более изящно). Другими словами, когда вы видите «динамическое программирование», вам нужно перевести его в «потрясающую оптимизацию».

Answer 2

'Динамическое программирование' не имеет ничего общего с динамическим распределением памяти или чем-то еще, это просто старый термин. На самом деле, это не имеет ничего общего с современным измерением «программирования».

Это метод решения определенного класса задач - когда оптимальное решение подзадачи гарантированно является частью оптимального решения более крупной проблемы. Например, если вы хотите заплатить 567 долларов США с наименьшим количеством счетов, решение будет содержать хотя бы одно из решений на сумму 1 .. 566 долларов США и еще один счет.

Код - это всего лишь приложение алгоритма.

Answer 3

Это динамическое программирование, потому что функция findCandidate разбивает предоставленный массив на более мелкие, более управляемые части. В этом случае он начинает с первого массива в качестве кандидата на большинство. Увеличивая счет, когда он встречается, и уменьшая счет, когда это не так, он определяет, верно ли это. Когда число равно нулю, мы знаем, что первые символы i не имеют большинства. Постоянно вычисляя локальное большинство, нам не нужно перебирать массив более одного раза на этапе идентификации кандидата. Затем мы проверяем, является ли этот кандидат на самом деле большинством, просматривая массив во второй раз, давая нам O (n). На самом деле он выполняется за 2n раза, так как мы повторяем дважды, но константа не имеет значения.