Я начинаю практиковать динамическое программирование, и я просто не могу обернуться вокруг этого вопроса:
Вопрос:
Ребенок бежит вверх по лестнице с n ступенями и может прыгать 1, 2 или 3 шага за раз. Реализуйте метод подсчета, сколько возможных способов ребенок может подняться по лестнице.
Решение взлома книги интервьюирования по кодированию выглядит так:
"Если бы мы думали обо всех путях к n-му шагу, мы могли бы просто построить их из путей к трем предыдущим шагам. Мы можем добраться до n-й остановки любым из следующих способов:
- Переход к шагу (n-1) и переход на 1 шаг
- Переход к шагу (n-2) и переход на 2 шага
- Переход на шаг (n-3) и прыжок на 3 шага "
Для этого, чтобы найти решение, просто сложите номер этих путей вместе!
Это то, что теряет меня! Почему ответ не такой: добавьте число этих путей, а затем добавьте 3? Поскольку, если вы находитесь на шаге n-1 или n-2 или n-3, есть 3 способа получить n-й шаг? Я понимаю, что если вы запишите ответы для первых 4 базовых случаев (при условии, что n = 0 вернет 1), вы увидите шаблон, подобный Фибоначчи. Но вы можете не видеть это, так что это сложно.
А потом они придумали этот код:
public static int countWaysDP(int n, int[] map) {
if (n < 0)
return 0;
else if (n == 0)
return 1;
else if (map[n] > -1)
return map[n];
else {
map[n] = countWaysDP(n - 1, map) + countWaysDP(n - 2, map) + countWaysDP(n - 3, map);
return map[n]; }
}
Итак, мой второй вопрос. Как это возвращает 1, когда n == 0. Даже если я принимаю этот факт, я все еще не могу найти способ решить это, если я возвращаю 0, когда n == 1.
Надеюсь, это имеет смысл.
Спасибо