Do you really need to regenerate the whole dynamic programming table though? It seems to me that it could be kept more conservative and only recalculate the needed parts.
So, for a landscape-oriented image of aspect ratio 2:1 that would mean re-calculating up to 50% of its pixels. For narrower ones, that percentage is even higher, so not too much to gain.