Comment by anderskaseorg

If you’re looking for a more practical algorithm: this problem can be formulated as a shortest path problem on the graph whose vertices are (n, fret, finger, string) tuples. A simple dynamic programming solution is to fill out a distance table whose entry distance[n, fret, finger, string] is the optimal cost of the prefix of the melody ending at note n, which can be computed as 0 if n = 1, or in terms of the entries for note n − 1 if n ≥ 2.