Описание тега dynamic-programming
Динамическое программирование - это алгоритмический метод эффективного решения проблем с рекурсивной структурой, содержащей множество перекрывающихся подзадач.
3
ответа
Смена монет (Динамическое программирование)
У меня есть вопрос о проблеме замены монет, когда нам нужно не только напечатать количество способов изменить $n с заданными номиналами монет, например, {1,5,10,25}, но также распечатать способы Например, если цель = 50 долларов, а монеты {1,5,10,25…
14 авг '17 в 06:54
1
ответ
Расслоение графа и DP
Расслоение графа является распространенным методом для работы с кратчайшим путем с некоторыми ограничениями. Вот описание этой техники: https://youtu.be/OQ5jsbhAv_M?t=47m7s. Итак, просто интересно, будет ли эта методика такой же, как при выполнении …
29 апр '17 в 21:28
2
ответа
Для данного массива длины n найдите число подмножеств, где XOR подмножества равно заданному числу.
Учитывая массив, arrдлины nнайти, сколько подмножеств arr есть такие, что XOR(^) из этих подмножеств равно заданному числу, ans, у меня есть это dp подход, но есть ли способ улучшить его временную сложность. ans всегда меньше 1024. Вот ans это нет. …
08 дек '15 в 05:34
1
ответ
Как собрать Windows Metro как панель инструментов?
Недавно я видел, как Windows 8 представляет на панели инструментов значки в стиле "Метро". На изображении выше кажется, что некоторые виджеты получают в 2 раза большую ширину по сравнению с другими, так что весь список виджетов в определенной степен…
10 окт '13 в 13:05
0
ответов
Динамический вызов процессору по типу запроса
Может быть, моя проблема проста, но я запутался, потому что я новичок в динамическом программировании. Вот проблема: у меня есть интерфейс, который называется IGame. и у меня есть два других интерфейса IGameRequest и IGameProcessor. public interface…
05 сен '18 в 16:31
1
ответ
Как эта функция C++ работает иначе, чем эквивалентная функция Java?
Я пытаюсь реализовать версию Java следующего алгоритма C++: void constructPrintLIS(int arr[], int n) { std::vector< std::vector<int> > L(n); L[0].push_back(arr[0]); for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if ((a…
19 апр '17 в 19:32
1
ответ
Перезапустите диалог из другого действия
У меня небольшая проблема, у меня есть диалог в одном действии с настраиваемым списком, который динамически генерируется с 1 текстовым представлением и 1 флажком в каждой строке. Когда я нажимаю флажок, он открывает другое действие для настройки чег…
20 фев '14 в 09:39
2
ответа
Хорошие игровые последовательности
Учитывая две игры A и B, и есть ограничения, что A можно играть в нечетные минуты, а B можно играть только в четные минуты. Как Play A на 1-й секунде, а затем на 3-й секунде, аналогично для B. Теперь хорошая последовательность определяется как: (1) …
13 авг '17 в 17:16
2
ответа
Как сложность уменьшается до O(n^2) от O(2^n) в случае запоминания?
В настоящее время я изучаю динамическое программирование с помощью техники запоминания и табулирования. Со ссылкой на следующую ссылку (самая большая проблема с возрастающей последовательностью) я не понял, как сложность уменьшается до O(n^2) с O(2^…
04 ноя '18 в 17:33
1
ответ
Нахождение Количество способов
Для заданных M цифр от 1 до 9 найдите количество способов сформировать число из N цифр, повторив одну или несколько заданных цифр таким образом, чтобы каждая из M цифр присутствовала в числе из N цифр хотя бы один раз. Пример, если М = 3 и N = 4 Отв…
03 окт '14 в 08:34
2
ответа
Динамическое программирование, находящее максимальное значение продуктов и сумму для элементов в массиве
Привет у меня есть следующая проблема, которую я хочу реализовать: заданный массив целых чисел: 1 2 7 5 1 2Я хочу найти максимальную сумму смежных товаров, т.е. 1+2+(5*7)+1+2 = 41 данный массив целых чисел: 1 2 4 2 4 2 Я хочу найти максимальную сумм…
11 дек '14 в 06:23
1
ответ
Наименьшая денежная сумма, которую можно получить, используя только монеты указанного достоинства, превышающие пороговое значение
Другими словами, дан набор из n натуральных чисел A и порог BЯ хочу найти самый маленький C чтобы: C > B C = A[1] * k[1] + A[2] * k[2] + ... + A[n] * k[n], k[i] целые числа>= 0 В качестве примера, если A = { 6, 11, 16 } тогда значения, которые мы…
09 янв '18 в 16:22
2
ответа
Самая длинная убывающая последовательность элементов в матрице
Я пытаюсь решить проблему, где мне нужно найти самую длинную убывающую последовательность элементов матрицы размера nxn, где последовательность S = (mi1j1, mi2j2, ·, ·, mikjk) такой, что ir mir+1jr+1 для всех 1 ≤ r , Я не могу думать о том, как подо…
19 окт '14 в 01:50
1
ответ
Почему эта параллельная функция для вычисления самой длинной общей подпоследовательности медленнее, чем последовательная?
Параллельное вычисление LCS следует схеме волнового фронта. Вот параллельная функция, которая медленнее, чем последовательная реализация. (Я думаю, что количество диагоналей (параллельных) и количество рядов (последовательных) как-то связано с этим)…
14 ноя '12 в 00:14
1
ответ
Алгоритм изменения монет: зачем добавлять 1?
Я имею в виду алгоритм замены монет. Я не могу понять рекурсивную формулу minCoins(sum) = min(minCoins(sum-values[i])) + 1, Почему мы должны добавить 1? Эта часть не ясна.
18 сен '16 в 15:01
2
ответа
Как использовать Манхэттен Расстояние, чтобы решить эту игру?
Каждый игрок по очереди убирает 1 или 2 банана из корзины из 50 бананов. Игрок, который опустошает корзину, побеждает. Какие веса следует использовать для расстояний и каким должен быть размер матрицы? Должна ли матрица меняться каждый раз, когда кт…
25 июн '17 в 12:10
3
ответа
Количество способов такое, что сумма k элементов равна p
Данная серия целых чисел, имеющих отношение, где число равно сумме двух предыдущих чисел, а начальное целое число равно 1 Серия ->1,2,3,5,8,13,21,34,55 найти число способов, чтобы сумма k элементов равнялась p. Мы можем использовать элемент любое ко…
13 май '16 в 04:57
4
ответа
Самая большая сумма шагов по n ступеням
Это проблема домашней работы, и это DP, но это не "сколько способов решить проблему n-лестницы". Скорее, в этой задаче каждому шагу лестницы присваивается номер от -10000 до 10000, поэтому, например, у меня есть такие шаги, как -1 2 1и я должен найт…
02 июн '15 в 05:25
0
ответов
Может ли известный алгоритм многоступенчатого графа для кратчайшего расстояния быть решен в порядке №. этапов?
Для тех, кто не уверен, что такое многоступенчатый граф: https://www.quora.com/Why-do-we-use-multistage-graph-problems-1 Пожалуйста, поделитесь своим алгоритмом, если вы можете решить его в порядке нет. этапов.
27 июн '16 в 17:20
1
ответ
Изменения: динамическое программирование
В предыдущей лекции нам сказали, что использование жадного подхода для решения проблемы изменения не всегда будет работать. Пример этого был приведен ниже: Мы хотим достичь n = 14и у нас есть три монеты разных ценностей: d1 = 1,d2 = 7,d3 = 10, Испол…
15 май '17 в 16:21