JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Dynamic Programming: From novice to advanced Dynamic Programming: From novice to advanced
 Dynamic Programming: From novice to advanced | Reply http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProgI've read this toutorial but I have a problem with the practice problem in the elementary section.Here is the problem statement:"Given an undirected graph G having N (1<=1000) vertices and positive weights. Find the shortest path from vertex 1 to vertex N, or state that such path doesn't exist. "Please help me to understand the problem statement and then introduce me a DP solution to solve it!Thanks a lot...
 Re: Dynamic Programming: From novice to advanced (response to post by Blackwizard) | Reply If I'm reading the problem statement right, it's just a single-source shortest paths problem in a positive weights graph. You can solve this with Dijkstra's algorithm. The algorithm does use dynamic programming, but I don't really consider it very representative of how dynamic programming problems look like in competition programming.However, in it's own right, the algorithm is important enough for you to get very familiar with it because it is useful for solving many problems.