live-coding
Жадность и динамика
Лестница, сумма подмассива, дома, монеты и возрастающая подпоследовательность. На российских секциях динамику спрашивают именно в этих формулировках.
Код можно запускать, разбор открыт. Внутри шага задачи усложняются, следующий шаг уже про другую формулировку.
Создайте аккаунт, чтобы видеть прогресс по треку.
Шаг 1. Память о предыдущем шаге
Число способов подняться по лестнице, одна сделка по акциям и максимальная сумма подмассива. Ответ в каждой позиции зависит от одного-двух предыдущих.
Шаг 2. Брать или пропустить
Грабитель домов, досягаемость прыжками и максимальное произведение подмассива. Прыжки укладываются в жадный максимум, произведение — в ту же схему суммы с учётом минуса.
Шаг 3. Сумма, строка, подпоследовательность
Сначала минимум монет, сразу потом число способов набрать ту же сумму: на собеседовании это два вопроса к одной таблице. Дальше декодирование цифр, разбиение строки по словарю и длина возрастающей подпоследовательности.