(В первый раз, когда я потер горячее место, я немного нервничал.)
Можно сказать, что динамическое программирование (динамическое программирование, указанное в далее, называемое DP), является одним из самых неприятных вопросов в интервью, а сам динамическое программирование - это вопрос интервью, который часто любит использовать многие крупные компании.
На самом деле, в проблеме конкурентного алгоритма динамическое программирование является очень удобной задачей, потому что сама проблема динамического программирования относительно больше зависит от подпрограмм, а компоненты, требующие гибкости и вдохновения, относительно невелики. В этой статье мы объясним ряд проблем с монетами, чтобы помочь вам ознакомиться с «процедурами» динамического программирования, чтобы вы могли лучше справляться с такими проблемами в будущих интервью.
Первый вопрос
有数目不限的1分，2分，5分的硬币，现要凑齐1元钱，有多少种凑法。
Это классический вопрос для интервью, и он мне очень нравится. Причина, по которой он подходит для вопросов для интервью, заключается в том, что это не вопрос, полностью зависящий от динамического программирования. Это может обеспечить хорошую степень различения, так что не возникнет неловкой ситуации, когда можно ответить «да» или «нет».
Прежде всего, давайте посмотрим на обычное решение.Самое простое, что можно придумать, это насильственный счет.Через тройной цикл подсчитайте количество способов помириться. код показывает, как показано ниже:
let r = 0;
for(let x = 0; x <= 100; x++)
for(let y = 0; y <= 50; y++)
for(let z = 0; z <= 20; z++)
if(x + 2 * y + 5 * z === 100)
++r;
console.log(r); //541
Но на самом деле и в этом обычном решении есть место для оптимизации, мы видим, что в номинале есть совершенно особое значение:1,это1Можно составить любое количество значений, и есть только один способ это сделать, поэтому нужно ли нам зацикливаться на этом 1? Ответ, конечно, нет. Мы можем написать такой код:
let r = 0;
for(let y = 0; y <= 50; y++)
for(let z = 0; z <= (100 - y * 2) / 5; z++)
++r;
console.log(r);
接下来，我们继续尝试优化这个平凡解，既然第二层循环，每次都必然加1，那么是否不需要循环，直接数出来呢？其实仔细看看这个循环，我们完全可以用除法搞定。 Окончательный код выглядит следующим образом:
let r = 0;
for(let y = 0; y <= 50; y++)
r += Math.floor((100 - y * 2) / 5) + 1;
console.log(r); //541
В этом плане оптимизация тривиального решения на самом деле близка к пределу, но если не учитывать особенности данных и обобщать на несколько монет любого номинала, есть ли хорошее решение? Давайте посмотрим на второй вопрос.
Продвижение второй темы
有数目不限的硬币，其面值存储于数组values当中，现要凑齐价值n，问有多少种凑法。
Обобщая первый вопрос, превращая константы в переменные, мы не можем воспользоваться особенностью данных.
Общая идея для всех задач динамического программирования заключается в том, что мы сначала уменьшаем масштаб проблемы, чтобы подумать, а затем думаем, как решить более крупный масштаб.Решения мелкомасштабных задач также могут служить основой для более масштабных задач.
Итак, сначала рассмотрим массивvaluesдлина1В случае , у нас есть только одна монета, котораяvalues[0], мы снова ограничиваем диапазон n, еслиnзначение меньше, чемvalues[0], то, очевидно, решения нет, еслиnзначение, равноеvalues[0], то есть решение.
Мы продолжаем стараться расширятьсяnмасштаб, мы можем легко найтиvalues[0]кратно , решение равно 1, иначе решение равно 0.
Что ж, этот вывод кажется бессмысленным и, очевидно, бесполезным. Но на самом деле это ключ к разгадке более масштабной проблемы.
Далее смотрим, предполагая, что массивvaluesдлина2, что просходит?
values[0]Мы уже обсудили ситуацию, дальше посмотримvalues[1], та же рутина, можем ли мы получитьvalues[1]Существует одно решение для кратных ? Подождите, кажется, мы что-то упустили, мы уже сделали выводvalues[0]Целое число, кратное , уже есть 1 решение.
Здесь нам нужно выпрыгнуть из присущей ему рамки мышления и рассмотреть, как возник вывод о «целократном».
values[0]2 раза, причина, по которой есть 1 решение, заключается в том, что вvalues[0]1 раз имеет 1 решение плюсvalues[0]публично заявить.values[0]3 раза, причина, по которой есть 1 решение, заключается в том, что вvalues[0]2 раза имеет 1 решение, основанное на добавленииvalues[0]Выходит... и так далее.
Мы можем представить,values[0]кратно , начиная с предыдущего «1 решения» и постоянно используяvalues[0]размер шага, перейти к новому узлу.
И даvalues[1]Например, на поле уже есть несколько узлов «1 решение», поэтому мы можем начать с 0 или начать сvalues[0]начиная с кратного , сvalues[1]за шаг вперед.
Так вот вопрос, а что если совпадение? В это время узел «1 решение» становится узлом «2 решения».
Следующий,values[2]прибытьvalues[3]Вот и все.
Мы используем эту идею, чтобы показать вам демонстрацию анимации (вы можете сделать это самиИзменить параметрыПроверить):
Наконец пишем код:
function countCoins(values, n) {
let table = new Array(n + 1).fill(0);
table[0] = 1;
for(let value of values) {
for(let i = value; i <= n; i++)
table[i] += table[i - value];
}
return table[n];
}
console.log(countCoins([1, 2, 5], 100)); //541
Вопрос 3 Ограничения
有若干的硬币，其面值存储于数组coins当中，以对象{value:number, count:number}表示其面值和数量，现要凑齐价值n，问有多少种凑法
Ну, с предыдущим основанием, давайте посмотрим, если мы ограничим количество монет одновременно, как это решить?
Легче всего придумать то же самое, что и предыдущую идею, начиная с 0.
Но когда код будет написан, мы обнаружим проблему, потому что количество монет ограничено, когда мы вычисляем номинал, мы должны различать, использовал ли узел текущий номинал, поэтому нам нужно сделать снимок монеты. предыдущий массив.
Итак, есть ли лучший способ?
Конечно, есть. На самом деле, пока мы поворачиваем цикл в обратном порядке, обновленный узел должен быть позади, и нет необходимости различать, был ли обновлен узел.
Окончательный код выглядит следующим образом:
function countCoins(coins, n) {
let table = new Array(n + 1).fill(0);
table[0] = 1;
for(let coin of coins) {
let {value, count} = coin;
for(let i = n; i >= 0; i--)
if(table[i] > 0)
for(let j = 1; j <= count && i + value * j <= n; j++)
table[i + value * j] += table[i];
}
return table[n];
}
console.log(countCoins([
{value:1, count:100},
{value:2, count:50},
{value:5, count:20}], 100));
4-я вариация
现有一堆硬币，欲将其分为两堆，使得两堆的差值尽量小，求其最小差值。
Наконец, давайте рассмотрим эту проблему укладки монет. На самом деле, когда мы решаем алгоритмические задачи, достигнув определенного уровня мастерства, сложность зачастую заключается не в так называемом «динамическом программировании», «жадности», «разделяй и властвуй» и прочих рутинах, а в абстракции и понимание проблемы.
Разделение на две стопки так, чтобы разница между двумя стопками была как можно меньше, на самом деле ничем не отличается от проблемы объединения денег. Определяется общая стоимость стопки монет, затем деление на две стопки — это собственно стоимость, а остальное — другая стопка. Если разница между двумя стопками должна быть как можно меньше, то следует надеяться, что полученное значение будет как можно ближе к 1/2 от общего значения.
Поскольку задачу можно преобразовать в задачу сбора денег, мы можем использовать процедуру четвертого вопроса, чтобы вычислить все значения, которые можно собрать ниже 1/2 от общего значения, а затем найти ближайший узел до 1/2 от общей стоимости.
На основе предыдущего вопроса мы можем использовать его как ответ на этот вопрос без изменения кода.
function countCoins(coins) {
let total = ((coins) => {
let r = 0;
for(let coin of coins) {
let {value, count} = coin;
r += value * count;
}
return r;
})(coins);
let n = Math.floor(total / 2);
let table = new Array(n + 1).fill(false);
table[0] = true;
for(let coin of coins) {
let {value, count} = coin;
for(let i = n; i >= 0; i--)
if(table[i] > 0)
for(let j = 1; j <= count && i + value * j <= n; j++)
table[i + value * j] = true;
}
for(let i = n; i >= 0; i--){
if(table[i])
return total - 2 * i;
}
}
console.log(countCoins([
{value:2, count:1},
{value:5, count:5}])); //3
мыслительные вопросы
Благодаря этой статье каждый должен был узнать общую рутину задачи о монете, но проблемы, обсуждаемые в этой статье, только рассчитаны и собраны, и нет конкретного решения для сбора денег.Заинтересованные студенты могут дополнить эту часть логики и отправить им поделиться в разделе комментариев.