Серия Simplify — Динамическое программирование №1 — Подъем по лестнице
Ссылка на Leetcode — https://leetcode.com/problems/climbing-stairs/
Вы можете задать этот вопрос, если у вас есть некоторый опыт динамического программирования, в противном случае продолжайте.
Описание вопроса: Вы поднимаетесь по лестнице. Чтобы добраться до вершины, требуется n шагов. Каждый раз вы можете подняться либо на 1, либо на 2 ступени. Сколькими различными способами вы можете подняться на вершину?
Input: n = 3 Output: 3 Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step
Вопросы динамического программирования могут показаться пугающими, если у вас нет организованного подхода. Многие учебные пособия представляют множество подходов в Интернете, все они работают и могут помочь вам в обучении. Вот как я это делаю -
- Давайте поместим несколько образцов символов, чтобы представить наш окончательный ожидаемый ответ. Допустим, каждый элемент в следующем массиве представляет количество шагов, предпринятых для достижения этого индекса.
Solution at index i -> a, b, c, d, e, f, ...... index -> 0, 1, 2, 3, 4, 5, ......
2. В приведенном выше примере давайте случайным образом выберем индекс. Это должно быть где-то посередине. Не крайности. Например, вы можете выбрать 2, 3 или 4. Допустим, в этом примере мы выбрали 4. Как мы могли достичь 4? Вопрос говорит, что мы можем сделать 1 или 2 шага. Итак, всего 2 варианта, как показано ниже. Другого прямого пути сюда нет.
3. Перечислим все возможности достижения 4. Мы можем достичь 4, либо сделав 1 шаг из 3, либо 2 шага из 2. Всего 2 возможных варианта достижения 4. Таким образом, количество способов достичь 4 равно сумме количества способов. чтобы достичь 3 и количество способов достичь 2. Это можно обобщить, количество способов достичь x равно сумме количества способов достичь x-1 и количества способов достичь x - 2. Или даже лучше Решение(x) = Решение(x-1) + Решение(x-2)
4. Это решает большую часть проблемы. Далее мы видим, что в основном мы можем вычислить это для любого числа, если мы знаем решение для x-1 и x-2. Это будет продолжаться до тех пор, пока вы не достигнете 0. Итак, пришло время определить или, скорее, вручную рассчитать и присвоить значения для базового случая.
- Решение (1) = 1, так как вы можете сделать 1 шаг от земли и дойти до 1-го шага. Невозможно сделать 2 шага вперед и достичь первого шага.
- Solution(2) = 2. Это хорошо объясняется в самой постановке задачи.
Вооружившись этой информацией, мы можем написать первое решение вроде этого —
public int solution(int n) {
// Handling base cases. Can be optimised, making this verbose intentionally
if(n == 0) return 0;
if(n == 1) return 1;
if(n == 2) return 2;
return solution(n-1) + solution(n-2); // Solution that we figured out in step 3
}
5. Это решение имеет все элементы и, вероятно, будет прекрасно работать во многих случаях. Здесь есть, правда, одна проблема.
- Решение(5) = Решение(4) + Решение(3)
- Решение(4) = Решение(3) + Решение(2)
6. Шаг 6 вызывает опасение, что когда мы вычисляем ответ для n = 5, нам нужен ответ для n = 4 и n = 3, и снова ответ для n = 4 снова требует ответа для n = 3. Итак, мы в конечном итоге делать одни и те же вычисления несколько раз. Вот тут нам и нужна оптимизация. Что, если бы мы могли вычислить каждый ответ один раз и сослаться на него, если его спросят снова. Это называется запоминание.
public int climbStairs(int n) {
if(n<=2)
return n;
int arr[] = new int[n+1];
arr[0] = 0; // Base case
arr[1] = 1; // Base case
arr[2] = 2; // Base case
for(int i=3;i<arr.length;i++){
arr[i] = arr[i-1] + arr[i-2]; // The solution we figured out in step 3
}
return arr[n];
}
7. В приведенном выше решении мы сохраняем старые результаты в массиве и повторно используем их при необходимости снова.
8. Прежде чем закончить, я резюмирую этот подход.
- Напишите образец данных на бумаге/экране и выберите случайный средний элемент для размышления. Этот числовой случайный индекс не должен быть слишком большим для любого конца массива.
- Для этого среднего элемента попробуйте сформулировать рекурсивное решение, взяв примеры и информацию из описания вопроса.
- Как только вы получите рекурсивное решение, найдите и рассчитайте решение для базовых случаев.
- Протестируйте решение, а затем добавьте массив или хэш-карту для хранения старых результатов.
Что еще? Тот же самый вопрос можно задать там, где предполагается сделать либо 1, либо 2, либо 3 шага. Интуиция остается почти такой же.
С вопросами динамического программирования трудно справиться, если мы не разберем его. После того, как вы разобрались, большинство вопросов можно свести к тому, чтобы собрать вещи вручную, попробовав несколько образцов.
Я буду продолжать добавлять больше вопросов. Следите за новостями. Спасибо
