Задача на динамическое программирование - Лесенка C++

Question

Вова стоит перед лесенкой из N ступеней. На каждой из ступеней написаны произвольные целые числа. Первым шагом Вова может перейти на первую ступень или, перепрыгнув через первую, сразу оказаться на второй. Так же он поступает и дальше, пока не достигнет N-ой ступени. Посчитаем сумму всех чисел, написанных на ступенях, через которые прошёл Вова.

Требуется написать программу, которая определит оптимальный маршрут Вовы, при котором, шагая, он получит наибольшую сумму.

Входные данные

В первой строке содержится натуральное число N — количество ступеней лестницы (2≤N≤1000). Во второй строке через пробел заданы числа, написанные на ступенях лестницы, начиная с первой. Числа, написанные на ступенях, не превосходят по модулю 1000.

Выходные данные

Выведите наибольшее значение суммы.

Получился следующий код

#include <iostream>
#include <vector>
using namespace std;
int dp(vector<int>&les, int k) {
    if (k == 1) {
        return les[0];
    } else if (k == 0) {
        return 0;
    }
    return max(dp(les, k-1) + les[k-1], dp(les, k-2) + les[k-1]);
}

int main() {
    int n;
    cin >> n;
    vector <int> lesnica(n);
    for (int i = 0; i < n; ++i) {
        cin >> lesnica[i];
    }
    cout << dp(lesnica, n);
}

Выдаёт ошибку, что "Программа выполнялась слишком долго и была прервана". Как ускорить?

Answer 1

Здесь рекурсия неуместна оттого, что при очень больших N получится слишком много вызовов, отсюда и недостаток времени.

Я предлагаю делать все необходимые вычисления с ДП прямо в цикле после ввода очередного элемента вектора — так будет точно следоваться линейное время выполнения. Если что, мы подставляем в дополнительную переменную максимум среди текущего элемента, суммы этого же элемента и прошлого и суммы этого же элемента с позапрошым:

#include <iostream>
#include <vector>

using namespace std;


int main() {
    int n;
    cin >> n;
    vector <int> lesnica(n);
    for (int i = 0; i < n; ++i) {
        cin >> lesnica[i];
        int temp = lesnica[i]; // для нормальной проверки без других заморочек
        if (i > 0) {
            temp = max(temp, lesnica[i] + lesnica[i - 1]);
            if (i > 1) {
                temp = max(temp, lesnica[i] + lesnica[i - 2]);
            }
        }
        lesnica[i] = temp;
    }
    cout << lesnica[n - 1];
}

Answer 2

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

Я просто добавил мемоизацию; программу на правильность не проверял.

#include <iostream>
#include <vector>
using namespace std;

const int SENTINEL = 10000000; // Указатель, что значение не просчитано
                               // (заведомо невозможное значение)
const int N = 1001;            // Заведомо достаточный размер массива значений

int dps[N];

int dp(const vector<int>&les, int k)
{
    if (dps[k] != SENTINEL) return dps[k];
    if (k == 1) {
        return les[0];
    } else if (k == 0) {
        return 0;
    }
    return dps[k] = max(dp(les, k-1) + les[k-1], dp(les, k-2) + les[k-1]);
}

int main() {
    for(int i = 0; i < N; ++i) dps[i] = SENTINEL; // Инициализация массива
    int n;
    cin >> n;
    vector <int> lesnica(n);
    for (int i = 0; i < n; ++i) {
        cin >> lesnica[i];
    }
    cout << dp(lesnica, n);
}

Для сравнения — на примере из 45 ступенек ваша программа считала примерно 6.5 секунд; моя дала на тех же исходных данных тот же ответ за 14 миллисекунд...

Answer 3

Когда Вова стоит на n-ой ступеньке стоимостью c(n) какую максимальную сумму s(n) он может набрать? Если он пришёл с предыдущей ступеньки, c(n) + s(n - 1). Если перепрыгнул через ступеньку, то c(n) + s(n - 2). Нам надо выбрать максимальную сумму, так что:

s(n) = max(c(n) + s(n - 1), c(n) + s(n - 2)) =
= c(n) + max(s(n - 1), s(n - 2))

Начальные условия: s(1) = c(1), s(2) = c(2) + max(s(1), 0).

Оказывается, чтобы вычислить следующую сумму надо знать ровно две предыдущие и стоимость следующей ступеньки. Это позволяет записать решение работающее в константной памяти:

#include <algorithm>
#include <iostream>

int main() {
    int n;
    std::cin >> n;
    int s1 = 0; // лучшая сумма предыдущей ступеньки
    int s2 = 0; // лучшая сумма предпредыдущей ступеньки
    for (int i = 0; i < n; ++i) {
        int c; // число на следующей ступеньке
        std::cin >> c;
        const int s0 = c + std::max(s1, s2);
        s2 = s1;
        s1 = s0;
    }
    std::cout << s1 << '\n';
}

БЛОГ НА HUSL

Задача на динамическое программирование - Лесенка C++

Ответы (3 шт):