Динамическое программирование - 4 клавиши клавиатуры

Question

Представьте, что у вас есть специальная клавиатура со следующими клавишами:

Клавиша 1: (A): печатать одну букву «А» на экране.

Клавиша 2: (Ctrl-A): выделение всего экрана.

Клавиша 3: (Ctrl-C): копирование выделения в буфер.

Клавиша 4: (Ctrl-V): печать буфера на экране, добавление его послето, что уже было напечатано.

Теперь вы можете нажимать клавиатуру только N раз (с четырьмя вышеуказанными клавишами), узнать максимальное число символов «А», которое вы можете напечатать на экране.

Пример 1:

Вход: N = 3

Выход: 3

Объяснение: Мы можем получить максимум 3 Анажмите следующую последовательность клавиш: A, A, A

Пример 2:
Ввод: N = 7

Выход: 9

Объяснение:Мы можем получить максимум 9 A на экране, нажав следующую последовательность клавиш: A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V

(ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: Я НЕ ХОЧУ СЛУШАТЬ РАЗНОЕ РЕШЕНИЕ. Я просто хочу понять, что яотсутствует и как это исправить.)

Вот мое текущее (неправильное) решение (пояснение ниже):

class Solution:
    def maxA(self, N):
        screen = [0] * N
        screen[0] = 1
        applied_clipboard = clipboard = select = 0        
        for i in range(1, N):
            if i < 3:
                screen[i] = screen[i-1] + 1
            else:
                screen[i] = max(screen[i-3] + clipboard, screen[i-1] + 1, screen[i-1] + applied_clipboard)

                if screen[i] == screen[i-3] + clipboard:
                    applied_clipboard = clipboard

            select, clipboard = max(select, screen[i-1]), max(clipboard, select)
        return screen[-1]

Есть несколько состояний, которые я отслеживаю, как вы можете видеть в приведенном выше коде.Состояния:

1. Сколько символов я выбрал?
2. Сколько символов я напечатал на экране?
3. Сколько символов в моем буфере обмена?
4. Какой самый последний буфер обмена, который я на самом деле применил?

С этими частями состояния я считаю, что могу принимать оптимальные решения на каждом этапе.

Однако мой код неверен.Для ввода N = 11 мой код возвращает 27, и правильное значение - 27.Однако для N=9 и N=10 правильными значениями являются 16 и 20 (соответственно), но я получаю 15 и 18 (соответственно).

Кто-нибудь видит ошибку в том, как я обновляю состояние?

РЕДАКТИРОВАТЬ.Отвечая на существующие ответы: Я понимаю, что мое обновление состояния может быть неполным, но вопрос в том, где.Моя идея здесь состояла в том, чтобы максимизировать каждый кусочек государства, поскольку существует отдельная серия решений для максимизации каждого кусочка государства.Затем используйте всю эту информацию для обновления состояния в следующей итерации.

Переписал мой код, чтобы сохранить состояние каждой части.

class Solution:
    def maxA(self, N):
        screen = [0] * N
        screen[0] = 1
        applied_clipboard, clipboard, select = [[0] * N for _ in range(3)]

        for i in range(1, N):
            if i < 3:
                screen[i] = screen[i-1] + 1
            else:
                screen[i] = max(screen[i-3] + clipboard[i-1], screen[i-1] + 1, screen[i-1] + applied_clipboard[i-1])

                if screen[i] == screen[i-3] + clipboard[i-1]:
                    applied_clipboard[i] = clipboard[i-1]
                else:
                    applied_clipboard[i] = applied_clipboard[i-1]

            select[i] = max(select[i-1], screen[i-1])
            clipboard[i] = max(clipboard[i-1], select[i-1])

        print('screen', screen)
        print('clipboard', clipboard)
        print('applied', applied_clipboard)
        return screen[-1]

Я думаю, что меня смущает то, как сохранить то, какое значение буфера обмена было применено (applied_clipboard) по сравнению с тем, каково максимальное состояние буфера обмена.Но мне нужно провести различие между ними, так как это влияет на повторяемость отношений.

Спасибо user3386109 за подсказку, что:

• Правильный ряд шагов для N=9 равен AAAASCVVV (всего 16 А)
• Мой код для N=9, выводит AAASCVVVV (всего 15 A).

, где s = выбор, c = копирование и v = вставка.

Answer 1

Ошибка, довольно просто, состоит в том, что код максимизирует количество символов «А» на экране на каждом шаге.Если вы print screen в конце функции, когда N равно 9, вы увидите это:

[1, 2, 3, 4, 5, 6, 9, 12, 15]

Обратите внимание, что когда N равно 6, максимальное число 'A наэкран 6. Это можно сделать тремя различными способами:

AAAAAA
AAscvv
AAAscv

, где s = select, c = copy и v = paste.

Однако, когда N равно 9,правильный ответ -

AAAAscvvv

. Как вы можете видеть, после 6 нажатий клавиш число «А» на экране составляет только 4, а не 6. Так что максимальное количество «А» на экране на каждом шагене дает правильного ответа.

Answer 2

Один из способов думать об этом может заключаться в том, что наше решение должно заканчиваться paste, поскольку очевидно, что мы не хотим тратить впустую прессы, заканчивая select или copy.Тогда мы можем предположить, что состояние экрана, из которого мы хотели бы вставить изображение, является оптимальным (в противном случае, зачем нам вставлять его?).

Пусть f(n) представляет максимальное число A с.можно вывести.Тогда мы могли бы многократно применять любое состояние экрана назад тремя нажатиями или более.Например, при 7-м нажатии мы можем оглянуться назад и сказать: чтобы повторить состояние экрана 4 (то есть всего 4), нам нужно 3 нажатия, поэтому при повторении из 4 наша запись будет длиться 7, 4 + 4 = 8 A с.,Если бы мы попытались повторить с 3, нам потребовалось бы 3 нажатия на 1 повторение, что привело бы к 6, и у нас все еще может быть еще 1, так что 3 + 2 * 3 = 9. Таким образом, повторное применение состояния экрана 3 предлагает записьза 7 девять A с, что является лучшим.Для любого 0 < j < i-3 мы можем получить 1 + i - (j + 3) + 1 или i - j - 1, умноженное на j состояние экрана.

Код JavaScript:

function f(n) {
  const m = [0,1,2,3,4,5,6].concat(
    new Array(Math.max(n-6,0)).fill(0));

  for (let i=7; i<=n; i++)
    for (let j=1; j<=i-3; j++)
      m[i] = Math.max(m[i], m[j]*(i-j-1));

  console.log(JSON.stringify(m));
  return m[n];
}

console.log(4, f(4));
console.log(7, f(7));
console.log(9, f(9));
console.log(10, f(10));
console.log(11, f(11));

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

Если это поведение является последовательным, это будет означать, что алгоритм имеет O(n) сложность.

function f(n) {
  const m = [0,1,2,3,4,5,6].concat(
    new Array(Math.max(n-6,0)).fill(0));

  for (let i=7; i<=n; i++){
    let prev = 0;
    for (let j=i-3; j>0; j--){
      let curr = m[j]*(i-j-1);
      if (curr < prev){
        console.log(`Early exit. n: ${n}, i: ${i}, j: ${j}`);
        break;
      }
      prev = curr;
      m[i] = Math.max(m[i], curr);
    }
  }

  console.log(JSON.stringify(m));
  return m[n];
}

console.log(50, f(50));

Answer 3

Как я вижу (теперь, когда я изменил код для запуска), вы корректно обновляете вещи.Я подозреваю, что проблема связана с неполным обновлением состояния.К сожалению, я думаю, что ваша реализация верна, но ваш алгоритм неверен.

Я думаю Ваша проблема в том, что screen обновляет каждую итерацию, замыкая ваши долгосрочные цели.На каждой итерации вы обрабатываете выбор так, как будто это нажатие клавиши должно быть последним.В результате вы иногда отказываетесь от буфера обмена с большим потенциалом и обновляете только то, что дает вам больше всего A с для этого шага.

Вам необходимо поддерживать несколько полезных состояний для каждого шага: не толькоВеликолепный экран, но также и потенциал богатого буфера обмена.

ОБНОВЛЕНИЕ Я думаю, что мы теперь вместе думаем.Вам необходимо иметь несколько состояний - частичных решений - для каждого количества нажатий клавиш.Это не прямое отношение повторения: это скорее квантовое состояние.

Например, при 7 нажатиях клавиш необходимо представлять как минимум два состояния.

• В результате AAAASCV,у вас 8 A с на экране, 4 в буфере обмена.(8, 4)
• В результате AAASCVV у вас есть 9 A с на экране, 3 в буфере обмена.(9, 3)

Ваш текущий алгоритм допускает только одно значение для screen и clipboard при каждом количестве нажатий клавиш.Он сохраняет только решение с лучшим краткосрочным результатом.Пропускает, что (8,4) будет лучшим трамплином для 9 и 10 нажатий клавиш.

Вам нужно сохранить все пары, которые не доминируют на каждом этапе.состояние G "доминирует" состояние H тогда и только тогда, когда G(screen) >= H(screen) и G(clipboard) >= H(clipboard).

---

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

scr   clip   sel
12      4     0          Nothing selected
12      3     0          Nothing selected
 9      3     9          Stopped at 9 A's and did a select-copy

Это третье состояние немедленно опередит первоедва для еще двух шагов.