У меня проблемы с концептуальным пониманием решения хорошо известной проблемы подъема по лестнице. Проблема n-лестницы:
У вас есть n шагов, чтобы подняться. Вы можете подняться только на 1 или 2 шага за раз. найдите количество способов достичь N-го шага.
Для простоты, давайте просто использовать случай, когда n = 2. Решение T(n) = T(n-1) + T(n-2), и это, конечно, последовательность Фибоначчи.
Объяснение , почему обычно выглядит примерно так:
Вы находитесь на n-м шаге. Как ты туда попал, если бы ты мог подниматься на 1 или 2 шага за раз? Ну, ваш предыдущий шаг должен быть либо шагом n-1 (шаг 1), либо шагом n-2 (шаг 2). Теперь есть T(n-1) способов достижения n-1-го шага и T(n-2) способов достижения n-2-го шага, что означает, что есть T(n-2) способов достижения n, если ваш последний шаг был на n-2 и T(n-1) способов достижения n, если ваш последний шаг был на n-1. Это единственные две возможности того, как вы наконец достигли n, поэтому общее количество способов добраться до n-го шага составляет T(n-1) + T(n-2)
У меня проблемы с концептуализацией приведенной ниже части:
есть T(n-1) способов достижения n-1-го шага и T(n-2) способов достижения n-2-го шага, что означает, что есть T(n-2) способов достижения n, если ваш последний шаг был на n-2 и T(n-1) способов достижения n, если ваш последний шаг был на n-1.
Это звучит неправильно. Похоже, что объяснение противоречит само себе.
Есть T(n-1) способов достичь n-го шага
и
и T(n-1) способы достижения n, если ваш последний шаг был на n-1
и аналогично для T(n-2)
Я также запутался во втором пункте. Когда мы говорим, что решение - T(n-1) + T(n-2), мой мозг кричит, но подождите минутку, вы считаете дважды. T (n-1) уже включает T (n-2) '.
Может ли кто-нибудь помочь мне концептуально понять причину, по которой T(n) = T(n-1) + T(n-2)
PS Это не вопрос относительно реализации решения, а скорее вопрос о том, как объяснить / понять ответ.