Can all or most combinatoric optimization problems in Machine Learning be solved using Viterbi algorithm? I am just scratching the surface of the topic but are there practical limitations even for Viterbi Algorithm? Also, are Viterbi Algorithm and dynamic programming equivalent?
 A: The Viterbi algorithm solves the problem of finding the most likely latent states for given a hidden Markov model with known transition probabilities. This is a very specific problem, whereas dynamic programming is a very general methodology for solving combinatorial optimisation problems. For example, Dijkstra's algorithm for finding the shortest path in a graph uses a dynamic programming approach but it doesn't involve probabilities at all so it's not really equivalent to the Viterbi algorithm.
Combinatorial optimisation arises in many other areas, for instance Mixed-Integer linear programming problems can arise when you want to do variable selection in SVMs and linear models. These can be solved with branch-and-bound type algorithms.  Another example is that maximum a posteriori inference in Markov random fields can be formulated as a max-cut problem which is often solved with the Edmonds–Karp algorithm. The Edmonds-Karp algorithm is a greedy type algorithm.
You can probably reduce a given combinatorial optimisation problem to a problem with a standard dynamic programming solution but in general it won't always be the best approach. It may be instructive to look at the "no free lunch" type theorems.
