Обновление
Хотя все приведенные ниже обсуждения по-прежнему полезны, ответ от גלעד ברקן предоставляет гораздо более хороший базовый алгоритм, который позволяет нам пропустить мой параметр min. (Я знал Я должен был это посмотреть!) Это понимание позволяет значительно улучшить производительность по сравнению с алгоритмом, использованным ниже.
Думайте о динамическом программировании (DP) как о простой оптимизациитехника, которая может ускорить определенные рекурсивные процедуры. Если ваши рекурсивные вызовы повторяются (как в случае с числами Фибоначчи), то сохранение их результатов может значительно ускорить вашу программу. Но основная логика все еще является рекурсивным вызовом. Итак, давайте сначала рекурсивно решим эту программу и посмотрим, где мы могли бы применить оптимизацию DP.
(8, 4) только с пятью решениями достаточно мало, что, даже если время является алгоритмически экспоненциальным, оно все еще, вероятно, управляемо. Давайте попробуем простую рекурсию. И сначала давайте построим вывод, а не посчитаем его, чтобы перепроверить, что мы все делаем правильно.
Эта версия основана на идее, что мы можем установить первое число в спискеотслеживая это значение как минимум для оставшихся элементов, а затем повторяя для оставшихся позиций. Наконец, мы попробуем еще раз с большим начальным числом. Таким образом, наряду с нашими n и k входами нам также потребуется сохранить параметр min, который мы начинаем с 1.
Вот одна из версий:
const f = (n, k, min = 1) =>
k < 1 || n < k * min
? []
: k == 1
? [[n]]
: [
... f (n - min, k - 1, min) .map (xs => [min, ...xs]),
... f (n, k, min + 1)
]
console .log (
f (8, 4) //~> [[1, 1, 1, 5], [1, 1, 2, 4], [1, 1, 3, 3], [1, 2, 2, 3], [2, 2, 2, 2]]
)
(Вы не указали языковой тег; если этот синтаксис Javascript ES6 неясен, мы можем переписать его в другом стиле.)
После этогокажется правильным, мы можем написать более простую версию для подсчета результатов:
const f = (n, k, min = 1) =>
k < 1 || n < k * min
? 0
: k == 1
? 1
: f (n - min, k - 1, min) + f (n, k, min + 1)
console .log (
f (8, 4) //~> 5
)
Но если мы собираемся попробовать больший набор, скажем, f (1000, 10) (который, согласно проверке, должен быть 886745696653253 1 ), это может занять немного времени, чтобы рассчитать. Наш алгоритм скорее экспоненциальный. Так что для этого есть два способа динамического программирования. Наиболее очевидным является восходящий подход:
const f = (_n, _k, _min = 1) => {
const cache = {}
for (let n = 1; n <= _n; n ++) {
for (let k = 1; k <= Math.min(_k, n); k++) {
for (let min = n; min >= 0; min--) {
cache [n] = cache[n] || {}
cache [n] [k] = cache [n] [k] || {}
cache [n] [k] [min] =
k < 1 || n < k * min
? 0
: k == 1
? 1
: cache [n - min] [k - 1] [min] + cache [n] [k] [min + 1]
}
}
}
return cache [_n] [_k] [_min]
}
console.time('time taken')
console .log (
f (1000, 10) //~> 886745696653253
)
console.timeEnd('time taken')
Найти правильные границы здесь сложно, если не по какой-либо другой причине, потому что рекурсия основана на возрастающем значении min. Вполне вероятно, что мы вычисляем вещи, которые нам не нужны по пути.
Это также уродливый код, теряющий элегантность и удобочитаемость оригинала, в то же время получая только производительность.
Мы все еще можемсохранить элегантность, запоминая нашу функцию;это нисходящий подход. Работая с функцией многократного использования memoize, мы можем использовать наше рекурсивное решение практически без изменений:
const memoize = (makeKey, fn) => {
const cache = {}
return (...args) => {
const key = makeKey(...args)
return cache[key] || (cache[key] = fn(...args))
}
}
const makeKey = (n, k, min) => `${n}-${k}-${min}`
const f = memoize(makeKey, (n, k, min = 1) =>
k < 1 || n < k * min
? 0
: k == 1
? 1
: f (n - min, k - 1, min) + f (n, k, min + 1)
)
console.time('time taken')
console .log (
f (1000, 10) //~> 886745696653253
)
console.timeEnd('time taken')
memoize превращает функцию, которая вычисляет свои результаты при каждом вызове, в функцию, которая вычисляет их только при первом обнаружении определенного набора входных данных. Эта версия требует, чтобы вы предоставили дополнительную функцию, которая превращает аргументы в уникальный ключ. Есть и другие способы написания, но они немного уродливее. Здесь мы просто превращаем (8, 4, 1) в "8-4-1", а затем сохраняем результат под этим ключом. Там нет двусмысленности. В следующий раз, когда мы вызовем (8, 4, 1), уже вычисленный результат будет мгновенно возвращен из кэша.
Обратите внимание, что существует соблазн попробовать
const f = (...args) => {...}
const g = memoize(createKey, f)
BuЭто не работает, если рекурсивные вызовы в f указывают на f. И если они указывают на g, мы уже перепутали реализацию, и f больше не является автономной, поэтому для этого нет особых причин. Таким образом мы пишем это как memomize(createKey, (...args) => {...}). Расширенные методы, которые предлагают альтернативы , выходят за рамки обсуждения здесь.
Выбор между восходящим и нисходящим DP является сложным вопросом. В вышеприведенном случае вы увидите, что восходящая версия работает быстрее для данного ввода. Есть некоторые рекурсивные издержки при вызове дополнительных функций, и в некоторых случаях вы можете быть подвержены ограничениям глубины рекурсии. Но иногда это полностью компенсируется нисходящей техникой, вычисляющей только то, что вам нужно. Снизу вверх вычислит все меньшие входные данные (для некоторого определения «меньший»), чтобы найти ваше значение. Сверху вниз будут рассчитываться только те значения, которые необходимы для решения вашей проблемы.
1 Шутка! Я нашел значение только после использования динамического программирования.