KarimElSheikh's blog

By KarimElSheikh, history, 9 years ago, In English

There are some few problems I came across like Fish and Virus synthesis which seem to have solutions with BFS traversal and typical DP minimization/maximization function. I want to practice this technique because normally when I think of coding a DP solution I only think of DFS traversal, any ideas of problems which are best solved using this technique?

EDIT: Just a clarification this DP style is usually a "Reverse" BFS Traversal of the states where we travel from the leaf nodes upwards level by level and converge to the final state

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Try UVa 10801 — Lift Hopping.
Also, there is a shortest path algorithm we Chinese-speaking competitive programmers like to use, called SPFA. It's an improved Bellman-Ford, but the algorithm can also be viewed as BFS+DP.
You can refer to this wiki article here Shortest Path Faster Algorithm