Представьте, что у вас есть танцевальный робот в n -мерном евклидовом пространстве, начиная с начала P_0= (0,0,...,0).
Робот может сделать m типы танцевальных движений D_1, D_2, ..., D_m
D_i является n -вектором целых чисел (D_i_1, D_i_2, ..., D_i_n)
Если робот делает танец движением i, чем его положение изменяется на D_i:
P_{t+1} = P_t + D_i
Робот может сделать любой из танцевальных движений столько раз, сколько он хочет и в любом порядке.
Пусть k-танец определяется как последовательность k шагов танца.
Ясно, что существуют m^k возможные k-танцы.
Нам интересно узнать множество возможных конечных положений k-танца, а для каждой конечной позиции, сколько k-танцев заканчивается в этом месте.
Один из способов сделать это:
P0 = (0, 0, ..., 0);
S[0][P0] = 1
for I in 1 to k
for J in 1 to m
for P in S[I-1]
S[I][P + D_J] += S[I][P]
Теперь S[k][Q] расскажет вам, сколько k-танцев заканчивается в позиции Q
Предположим, что n, m, |D_i| малы (меньше 5), а k меньше 40.
Есть ли более быстрый способ? Можно ли как-то вычислить S[k][Q] "каким-то образом связанным с линейной алгеброй трюком? или какой-либо другой подход?
