Динамическое программированеи — один из важнейших навыков в работе для практически любого разработчика. Например, если вы хотите разработать новый веб сайт, или андроид приложение, или даже кастомную 1С-конфигурацию, вы обязательно стоклнетесь с динамическим программированием. Давайте же узнаем, как можно улучшить этот навык.
Ладно, шутки шутками, но Dynamic programming (DP) действительно нужно нам на собеседованиях. По сути, это один из главных типов задач из medium-hard, которые нужно уметь решать на leetcode собеседованиях. Можно относится к этому по всякому, но таковы правила игры, нам просто нужно адоптироваться и побеждать.
Последние несколько недель я пытался улучшить свои навыки DP. Скажу честно — это моя слабая тема. Даже на medium DP задачах я почти всегда встаю в тупик, и без hint со стороны сайта, или подсказки из решений — не могу найти верное решение. Про hard DP задачи я даже не говорю — совсем не выходит их решать. Поэтому я решил, пока есть свободное время, немного порешать задачи из этой сферы, немного набить руку, чтобы улучшить свои решения с типичной экспоненты (любимый Brute-force через рекурсию), на хотя бы полином через рекурсию с мемоизацией.
Далее я хочу опубликовать набор ссылок, книг и курсов, которые на мой взгляд достойны внимания. Я не буду приводить что-то банальное, типа Алгоритмы: построение и анализ (Кормен), потому что эта книжка просто улучшает вашу теоретическую базу, а не готовит к типичным собеседованияем. То есть, да, прочитать ее стоит в свободное время, но это не самый быстрый путь набить руку на DP.
Я не скажу, что стал сильно лучше разбираться в теме DP за последние пару недель. Однако все равно какой-то минимальный прогресс есть. Говорят, что чтобы стать крутым в DP, нужно просто решать решать задачи DP (хо-хо, заметили каламбур?? рекурентное соотношение, хохо).
Категории: Программирование