알고리즘 도움을 받고자 올립니다.

이런 문제를 풀고 있는데요, (대회문제는 아니라 비슷한 형태로 써볼게요)
Location N 개가 있고 t 시점에 Location 간의 이동할 확률은 Array 로 주어진다.
John 은 0 번에서 출발해서 이동한다.
t = x 시점에서 John 이 있을 가장 확률이 높은 위치를 구하시오.

예를 들어, 장소는 4개고 1번 장소에서 출발하는 이동확률은 다음과 같이 Nt Array 로 주어집니다.
t 1 2 3 4
0 {0.7, 0.5, 0.3, 0.1}
1 {0.1, 0.2, 0.3, 0.6}
2 {0.1, 0.3, 0.3, 0.1}
3 {0.1, 0.0, 0.1, 0.2}
이런 2차원 Array 가 각 장소마다 주어지죠.
세로줄은 t 시점에 각 장소로 이동할 확률이라 합이 항상 1 이고,
첫 출발은 0 번 위치에서 1.0 의 확률을 가지고 시작합니다.
t 가 한칸 지나면 0번 위치부터 순서대로 0.7, 0.1, 0.1, 0.1 확률을 갖게 되는 식으로요.

여기서 Transition 확률이 절대적 시간으로 주어진다면
아래 그림처럼 t = i 시점에서 각 노드에 있을 확률을 transition 확률과 곱해주면서 t = i + 1 노드에 누적합시키면 Forward Algorithm 으로 될 거 같은데요.
Complexity 는 O(tN^2) 가 되구요.

문제는 Transition 확률이 장소에 도착한 시점에 따라 상대적으로 적용되는 확률로 주어집니다.
위에 예에서 현재 시간은 t=3 이라고 하면 0번에서 0번으로 갈 확률은,
0 번 장소에 t=1 일 때 0.5 의 확률을 가지고 들어온 애는 두번째 열인 0.5 를 써야 되구요.
0 번 장소에 t=2 일 때 0.3 의 확률을 가지고 들어온 애는 첫번째 열인 0.7 을 써야 되는 식입니다.
현재 장소에 도착한 시점 t 도 알고 있어야 되는거죠.
열심히 생각한 바로는 아래 그림처럼 각 Node 마다 t 에 대한 State 가 하나 더 추가되서,
Complexity 가 O(t^2 N^2) 이 되야 되는거 같은데요.

더 빠르게 풀 수 있는 방법은 없을까요 ?
상대적 시간으로 주어지는 이동확률 Array 들을 절대적 시간으로 바꿀 수 있다면,
(0번 장소에 언제 도착했던지 간에 현재시간 t=3 에서 t=4 로 갈 확률을 구할 수 있다면,)
O(tN^2) 로 풀 수 있을거 같은데, 열심히 머리를 굴려봐도 수학적으로 바꾸는게 가능한지 모르겠네요 ;;