Viterbi Best Path Metric

Problem

Run the Viterbi dynamic program over a sequence of transition metric matrices. step_metrics[t][i][j] is the cost of moving from state i to state j at time t, the path starts in state 0 with metric 0 and all other states at infinity, and every state keeps the minimum accumulated cost. Return the minimum final path metric as an integer.

Hint

Each step keeps, for every state, the cheapest incoming path in add-compare-select fashion.

Test cases

case 1

in: [[[[0,1],[2,0]],[[1,0],[0,1]]]]

expected: 0

case 2

in: [[[[0,2],[1,0]]]]

expected: 0

case 3

in: [[[[0,1],[2,0]],[[1,0],[0,1]],[[0,0],[1,1]]]]

expected: 1

case 4

in: [[[[0,5],[5,0]],[[5,0],[0,5]]]]

expected: 0

Starter codePython

def viterbi_best_metric(step_metrics):
    # Your code here
    pass

4 test cases · run your code against them in the editor