Вот еще одна проблема из области динамического программирования, которую много раз задавали в интервью с небольшими вариациями. Постановка задачи довольно проста.
У вас есть лестница с n ступенями. У каждого шага есть своя стоимость, вы можете подняться на 1 или 2 шага за раз с любого шага. Единственным ограничением является то, что когда вы переходите с шага, вы должны оплатить стоимость, связанную с этим шагом.
Например, вы находитесь на 5-й ступени лестницы, и стоимость 5-й ступени составляет 12 долларов. Теперь по правилам вы можете прыгнуть либо на 6-й шаг, либо на 7-й шаг, но любой из этих прыжков будет стоить вам 12$. Теперь ваша цель - достичь вершины этажа с минимальными затратами. Вам будет предоставлен массив длины n, содержащий стоимость, связанную с n шагами.
Решение
Чтобы найти решение проблемы, важно сначала понять проблему. Если вы не понимаете, вы можете получить либо неправильное решение, либо вообще никакого решения. Теперь в этой проблеме несколько ключевых моментов, по которым вы должны иметь четкое представление.
- Начальная точка и конечная точка (верхний этаж) не являются частью ступени лестницы и, следовательно, с ними не связаны никакие затраты.
- Вы должны оплатить стоимость, связанную с шагом, только когда вы хотите перейти с этого шага, а не при достижении шага.
- Вы можете двигаться только на 1 шаг или 2 шага за раз.
- Вам будет предоставлен массив costдлиной n, а cost[i] — это стоимость i-го шага. .
Поскольку вы извлекли ключевые моменты, пришло время начать работу над решением. Лучше иметь ручку и дизайн и попробовать возможные подходы к решению, чем прямо писать код.
Наша цель - достичь вершины этажа и с минимальными затратами. Теперь ваша общая стоимость шага зависит от того, откуда вы пришли и достигли этого шага.
Пусть TotalCost(n) — это общая стоимость достижения n-й ступени лестницы от земли, тогда есть только две возможности: либо вы идете с (n-1)-й ступени, либо с (n -2)й .
Если вы переходите с (n-1)-го шага
Общая стоимость(n) = стоимость[n-1] + общая стоимость(n-1)
Если вы переходите с (n-2)-го шага
Общая стоимость(n) = стоимость[n-2] + общая стоимость(n-2)
Минимум из этих двух является нашим ответом, чтобы достичь n-го шага с минимальными затратами.
В нашей задаче добраться до верха этажа можно двумя способами.
С n-го шага или с (n-1)-го шага
Нашим ответом будет минимальная общая стоимость достижения этих двух шагов.
Когда n=1 означает, что общая стоимость достижения первого шага от земли будет равна нулю.
Когда n=2, общая стоимость достижения второго шага равна нулю с земли, потому что вы можете прыгнуть с земли на 2 шага, чтобы добраться до второго шага без каких-либо затрат.
Таким образом, конечными условиями для рекурсии являются n=1 и n=2.
int TotalCost(int n){
if(n==1||n==2)
return 0;
return min((TotalCost(n-1) + cost[n-1]),(TotalCost(n-2)+cost[n-2]));
}
Как вы можете видеть, расчет TotalCost(n) зависит от Total Cost(n-1) и Total Cost(n-2).
Далее TotalCost(n-1) зависит от расчета TotalCost(n-2) и TotalCost(n-2)
Мы вычисляем TotalCost(n-2) 2 раза, это известно как перекрывающиеся подзадачи.
Всякий раз, когда у вас есть перекрывающиеся подзадачи, вы можете использовать запоминание, чтобы избежать ненужных вычислений.
Давайте используем запоминание для оптимизации нашего решения.
vector<int> mem(n,-1);
int TotalCost(int n,vector<int>& mem){
if(n==1||n==2)return 0;
if(mem[n]!=-1)return mem[n];
mem[n] = min((TotalCost(n-1)+mem[n-1]),(TotalCost(n-2)+mem[n-2]));
return mem[n];
}
В приведенном выше коде мы используем вектор для хранения результатов, которые можно использовать в последующих итерациях.
Все элементы вектора инициализируются значением -1, чтобы мы могли отслеживать, был ли выполнен расчет для этого индекса или нет.
Приведенный выше код выполнит нашу работу, и он также достаточно эффективен по сравнению с рекурсивным решением, но все же есть много возможностей для оптимизации.
Даже с запоминанием этот код использует рекурсию, которая сама по себе использует пространство O(n) и использует дополнительную память O(n) для хранения промежуточных результатов.
Другой подход к решению этой проблемы состоит в том, чтобы идти снизу вверх, а не сверху вниз, этот подход позволит вам еще больше сократить требования к памяти до минимума.
В нашей задаче на каждом шаге нам нужно иметь два последних вычисления для вычисления, лучше отслеживать последние два вычисления, а не хранить в памяти все промежуточные результаты. У нас может быть две переменные, которые могут содержать два последних результата, и на каждой итерации эти две переменные могут обновляться, чтобы содержать два последних результата. В приведенном ниже коде используется временная сложность O (n) и пространство O (1).
int TotalCost(n) { if(n==1 || n==2 )return 0; int f1=0; int f2=0; for(int i=2;i<n;++i) { int f3 = min(f1+cost[i-2],f2+cost[i-1]); f1=f2; f2=f3; } return f2; }