Вот еще одна проблема из области динамического программирования, которую много раз задавали в интервью с небольшими вариациями. Постановка задачи довольно проста.

У вас есть лестница с 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;
}