Блог пользователя KarimElSheikh

Автор KarimElSheikh, история, 9 лет назад, По-английски

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

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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