Ссылка на задачу — 2140. Solving Questions With Brainpower.
📋 Описание задачи
- Дан вектор
questions (questions[i] = [pointsi, brainpoweri]).
- Вы проходите тест, состоящий из последовательности вопросов.
- Если вы решаете вопрос
i, то зарабатываете pointsi баллов, но пропускаете следующие brainpoweri вопросов.
- Вопросы можно пропускать
- Нужно определить, максимальное количество баллов, которое можно набрать, действуя оптимально.
📌 Пример:
- Вход:
questions = [[3, 2], [4, 3], [4, 4], [2, 5]]
- Размышления:
- Если решить вопрос
0, вы получите 3 очка и пропустите вопросы 1 и 2, перейдёте сразу к 3 → итого: 3 + 2 = 5.
- Если пропустить
0 и решить 1, вы получите 4 очка и пропустите 2 и 3 → итого: 4.
- Если пропустить
0 и 1, решить 2 → получите 4 очка, но пропустите 3 → итого: 4.
- Если пропустить
0–2 и решить 3 → получите 2 очка.
🔎 Оптимальная стратегия: решить вопросы 0 и 3, что даст нам 5 баллов на экзамене.
- 👉 Ответ:
5.
💡 Идея
Решение задачи требует на каждом шаге выбора между:
- Пропуском текущего вопроса и переходом к следующему (
i + 1).
- Решением текущего вопроса и переходом к вопросу после "перерыва" (
i + brainpower + 1).
Если двигаться с конца к началу, можно заранее знать, какой результат нас ждёт после любого выбора.
Это делает задачу идеально подходящей для динамического программирования в обратном (реверсивном) порядке вычислений.
🔧 Подробности подхода
- Создаём массив
dp длиной n + 1 (dp[i] — максимум очков, которые можно набрать, начиная с вопроса i).
- Обходим
questions в обратном порядке
- Для каждого вопроса:
- Вычисляем индекс
next, с которого можно продолжить после решения текущего.
- Вычисляем два варианта:
take = points + dp[next] — если решаем.skip = dp[i+1] — если пропускаем.
- Обновляем
dp[i] как max(take, skip).
- Финальный ответ в
dp[0].
📈 Асимптотики
- Время:
O(n) — каждый вопрос обрабатывается один раз.
- Память:
O(n) — массив dp длиной n + 1.
🧾 Исходный код
impl Solution {
pub fn most_points(questions: Vec<Vec<i32>>) -> i64 {
let n = questions.len();
let mut dp = vec![0i64; n + 1]; // dp[i] = max points starting from question i
questions.iter().enumerate().rev().fold(dp[n], |acc, (idx, vec)| {
let [points, brainpower] = vec[..] else { unreachable!("unexpected input format") };
let next = n.min(idx + brainpower as usize + 1);
let take = points as i64 + dp[next]; // Solve this question
dp[idx] = acc.max(take); // Max between solving and skip strategies
dp[idx]
})
}
}
Tags: #rust #algorithms #dynamic #dp #optimization