Задача о кузнечике

[irvind25]

Здравствуйте.
Есть задачка:
Дан абстрактный кузнечик, и абстрактная бесконечная трехмерная сетка, в узлах которой может находится кузнечик. Кузнечик находится в узле с координатами (0,0,0). Перемещается он может на одну клетку в 6-ти направлениях: вверх, вниз, вправо, влево, вперед, назад.
Также дано число n (0 <= n <= 200). Нужно найти количество возможных последовательностей перемещений кузнечика, так, чтобы его путь состоял из 2*n шагов, и начинался из нач. точки и заканчивался там же. Но во конечную точку при перемещении он может посетить только один раз.

Никак не могу сообразить, какие есть адекватные пути/алгоритмы решения этой задачи. Не подскажите?

чо тут думать. элементарная задача на динмическое программирование. считаешь для каждой клетки число путей каждой длины в неё из нуля не проходящие дважды через ноль, затем суммируешь для каждой клетки число путей длины n умножить на число путей 200-n.

и еще поделить на что-то надо чтобы не пересчитаться, но это мелочи реализации. идея, думаю, ясна