Всем привет! Есть задача: Конь стоит в левой нижней клетке поля размером n * n. Посчитать количество способов добраться до правого верхнего угла ровно за k ходов. Конь стандартный, т.е. ходит на две клетки в любом направлении и затем на одну в перпендикулярном(тоже в любом направлении). n, k <= 10; Доска пронумерована как матрица(от 1 до n сверху вниз и с 1 до n слева направо)
Пишу динамику dp[cnt][i][j] = количество способов сделав cnt ходов добраться до клетки (i, j). Вот решение, протестировать негде поэтому спрашиваю тут! Оно верное???
Напишите перебор и проверьте. Асимптотика всего лишь O(8k).
k ≤ 10
810 = 230
И что? За минуту-две в худшем случае спокойно отработает.
меньше чем за 10 сек отработал на всех размерах от 1 до 10 и на всех ходах от 1 до 10!
а на КФ меньше чем за секунду!
Линк Это не совсем то, но для решения требуется практически та же идея.
написал перебор, ответы совпадают. я то был почти уверен что это верно, но преподаватель(не мой) сказал, это неверно! и вот сейчас я догоняю, что преподаватель походу ждал решение перебором и скорее всего даже не слышал про ДП!
Никогда не доверяйте преподавателям
Кто знает, может цель данного урока — отстоять свою точку зрения? Университет — школа жизни, алгоритмы можно и в интернете выучить.