Задание относительно, динамическое программирование.Сделать мой код более эффективным?

Question

У меня есть задание, касающееся динамического программирования.Я должен разработать эффективный алгоритм, который делает следующее: есть путь, покрытый пятнами.Пользователь может двигаться вперед до конца пути, используя серию кнопок.Есть 3 кнопки.Один продвигает вас вперед на 2 точки, один продвигает вас вперед на 3 точки, один перемещает вас вперед на 5 точекПятна на пути черные или белые, и вы не можете приземлиться на черное пятно.Алгоритм находит наименьшее количество нажатий кнопок, необходимое для достижения конца (после последней точки можно его перескочить).Пользовательские вводы для "n", количество мест.И заполните массив n количеством B или W (черный или белый).Первое пятно должно быть белым.Вот то, что я имею до сих пор (это только псевдо):

int x = 0
int totalsteps = 0
n = user input
int countAtIndex[n-1] <- Set all values to -1 // I'll do the nitty gritty stuff like this after 
int spots[n-1] = user input

pressButton(totalSteps, x) {
    if(countAtIndex[x] != -1 AND totalsteps >= countAtIndex[x]) {
        FAILED } //Test to see if the value has already been modified (not -1 or not better)
    else
        if (spots[x] = "B") {
            countAtIndex[x] = -2 // Indicator of invalid spot
            FAILED }
        else if (x >= n-5) { // Reached within 5 of the end, press 5 so take a step and win
                GIVE VALUE OF TOTALSTEPS + 1 A SUCCESSFUL SHORTEST OUTPUT 
                FINISH }
        else
            countAtIndex[x] = totalsteps
            pressButton(totalsteps + 1, x+5) //take 5 steps
            pressButton(totalsteps + 1, x+3) //take 3 steps
            pressButton(totalsteps + 1, x+2) //take 2 steps
}

Я ценю, что это может выглядеть довольно плохо, но я надеюсь, что с этим все в порядке, я просто хочу убедиться, что теория звучит раньшеЯ пишу это лучше.Мне интересно, если это не самый эффективный способ решения этой проблемы.В дополнение к этому, где есть заглавные буквы, я не уверен, как «Сбой» программы или как вернуть «Успешное» значение.Любая помощь будет принята с благодарностью.

Я должен добавить incase, это неясно, я использую countAtIndex [], чтобы сохранить количество ходов, чтобы добраться до этого индекса в пути.Т.е. в позиции 3 (countAtIndex [2]) могло бы быть значение 1, означающее, что для его перемещения требуется 1 ход.

Answer 1

Я преобразую свой комментарий в ответ, так как это будет слишком долго для комментария.

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

Итак, в качестве примера предположим, что первые 11 элементов входного массива:

index:  0 1 2 3 4 5 6 7 8 9 10 ...
spot:   W B W B W W W B B W B  ...

Чтобы решить проблему, мы создаем выходной массив (он же таблица DP), чтобы хранить информацию, которую мы знаем о проблеме. Первоначально все значения в выходном массиве установлены в бесконечность, за исключением первого элемента, который установлен в 0. Таким образом, выходной массив выглядит следующим образом:

index:  0 1 2 3 4 5 6 7 8 9 10 ...
spot:   W B W B W W W B B W B
output: 0 - x - x x x - - x -

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

Затем мы выполняем итерацию с начала таблицы, обновляя записи по мере продвижения.

Из индекса 0 мы можем достичь 2 и 5 одним ходом. Мы не можем перейти к 3, потому что это место черное. Таким образом, обновленный выходной массив выглядит так:

index:  0 1 2 3 4 5 6 7 8 9 10 ...
spot:   W B W B W W W B B W B
output: 0 - 1 - x 1 x - - x -

Далее мы пропускаем индекс 1, потому что пятно черное. Итак, мы переходим к индексу 2. Из 2 мы можем достичь 4,5 и 7. Индекс 4 еще не достигнут, но теперь его можно достичь за два хода. Прыжок с 2 до 5 достигнет 5 за два хода. Но 5 уже может быть достигнуто за один ход, поэтому мы не будем его менять (именно здесь возникает рекуррентное соотношение). Мы не можем перейти к 7, потому что это черный. Поэтому после обработки индекса 2 выходной массив выглядит так:

index:  0 1 2 3 4 5 6 7 8 9 10 ...
spot:   W B W B W W W B B W B
output: 0 - 1 - 2 1 x - - x -

После пропуска индекса 3 (черный) и индекса обработки 4 (может достигать 6 и 9), мы имеем:

index:  0 1 2 3 4 5 6 7 8 9 10 ...
spot:   W B W B W W W B B W B
output: 0 - 1 - 2 1 3 - - 3 -

Обработка индекса 5 не изменит ничего, потому что 7,8,10 все черные. Индекс 6 ничего не меняет, потому что 8 черный, 9 уже может быть достигнут за три хода, и мы не показываем индекс 11. Индексы 7 и 8 пропускаются, потому что они черные. И все переходы из 9 в части массива, которые не показаны.

Так что, если целью было достичь индекса 11, число ходов было бы 4, а возможные пути были бы 2,4,6,11 или 2,4,9,11. Или, если массив продолжится, мы просто продолжим итерацию по массиву, а затем проверим последние пять элементов массива, чтобы увидеть, у кого наименьшее количество ходов.