Це питання мені було задано в інтерв'ю таце бентежно розкрило мої недоліки динамічного програмування. Я буду вдячний, якщо хтось може допомогти мені зламати цей. Крім того, мені було б дуже корисно, якщо ви можете пояснити свій процес мислення, коли ви розробляєте рішення, як я, здається, зможу зрозуміти, коли я бачу рішення, яке використовує парадигму динамічного програмування, але намагаюся прийти з моїм власним.
Без зайвої приналежності, ось питання, яке мені було задано.
Дано ціле число i і встановити X від k окуляри x1, x2, ... xk на реальній лінії виберіть i бали з набору X щоб мінімізувати суму відстані від кожної точки в X до точки в i з використанням динамічного програмування.
Відповіді:
7 для відповіді № 1У більшості проблем з ДП я намагаюся знайти такий собівідношення скорочення і перемоги. Тобто, це стосунок, за допомогою якого я можу відрізатись від розміру проблеми з кожним кроком (наприклад, ділити та перемагати, але зазвичай це не ділить проблему, це просто видаляє невелику частину). У цій проблемі (як і у багатьох інших) ми можемо зробіть дуже просте спостереження: або перша точка знаходиться у множині i балів, або це не "т.
Деякі позначення: Скажімо, X = {x1, x2, ..., xк}, і позначаємо скорочений набір Xн = {хн, xn + 1, ..., xк}.
Отже, спостереження полягає в тому, що або x1 є одним з i очок, або це не "т. Давайте" назвемо наші iфункція пошуку MSD (i, Xк) (мінімальна сума відстаней). Ми можемо висловити це відсічне спостереження наступним чином:
MSD (i, Xк) = Або MSD (i-1, Xk-1) U {x1} або MSD (i, Xk-1)
Ми можемо формалізувати частину "або"реалізуючи простий спосіб перевірити, який з цих двох варіантів насправді є: ми пробігаємо множину X і обчислюємо суму відстаней і перевіряємо, яка насправді менша. Зауважимо, що цей чек має час роботи ki оскільки ми будемо наївно пробігати кожен із k очок і схопіть мінімальну відстань від точок у наборі розміру i.
Ми робимо два простих спостереження щодо базових випадків:
MSD (i, Xя) = Xя
MSD (0, Xн) = {}
Перше - це те, що шукають i балів у наборі розміру i ми, очевидно, просто беремо весь набір.
Друга полягає в тому, що, шукаючи точки в множині, ми повертаємо порожній набір. Це індуктивно забезпечує, що MSD повертає набори розмірів i (це правда для випадку, коли i=0 і за індукцією вірно, згідно з нашим визначенням MSD вище).
Це все. Це знайде відповідний набір. Складність виконання є верхньою межею O(ik * step) де крок наш O(ik) перевірити зверху. Це пояснюється тим, що MSD запускатиметься за параметрами, які варіюються від 0-i і X1 - Xк, що в цілому становить ik можливі аргументи.
Це залишає нам час виконання O ((ik)2)
Наступна частина заснована на моєму розумінні питання ОП. Я не впевнений, чи відстань кожної точки в X від підмножини i розміру є сумою відстаней кожної точки від кожен інший пункт у підмножині, або сума відстаней кожної точки X від самої підмножини.
І.е. сигма x в X of (сума відстаней x від кожної точки в підмножині) OR sigma of x in X of (відстань x від підмножини, яка є мінімальною відстані від x до будь-якої точки підмножини)
Я припускаю останнє.
Ми можемо скоротити час виконання, оптимізуючи O(ik) перевірити зверху. Ми помічаємо, що елементи насправді сортуються (хоча і в зворотному порядку в цій нинішній нотації), оскільки коли ми додаємо їх, ми робимо це завжди з правого боку. Якщо припустити, що вони "відсортовані для початку, вони колись вийдуть із звичайної MSD. Якщо вони не були відсортовані для початку, ми можемо їх сортувати, що коштуватиме лише O(klogk) все одно.
Після сортування перевірятиметься відстань кожної точки від точки в наборі k * logi оскільки для кожного пункту ми виконуємо двійковий пошук. Це дає загальний час роботи O(ik * klogi + klogk)
= O (k2 * ілоги).
Нарешті, ми можемо виразити це як O (k3лог). Не найшвидше рішення, а рішення.
Я впевнений, що є ще більше оптимізацій, але це мій 2с.