title: Minimizing cost of pipeline by finding optimal locations for stations using dynamic programming
body: <p>I have a question about dynamic programming that I am trying to describe an algorithm for.</p>
  
  <p>Question:
  A pipeline is to be built and you have to decide on the optimal location of the stations along the path that has already been decided. The pipeline connects points x1 and xn and goes through locations x2,x3...x(n-1). There are stations at x1 and xn but part of the problem is to decide whether to build a station at point xi for i = 2,3...n-1.If a station is built the associated cost is bi and if a pipeline is built between stations xi and xj, the corresponding cost is cij. The total cost is the sum of the costs of the station and the corresponding pipeline section costs. The goal is to decide the optimal location of stations so that the total cost is minimized.</p>
  
  <p>We have to describe a general algorithm for this using dynamic programming. 
  My approach was to treat this like a rod cutting problem and try to make a matrix and minimize the cost but I am not sure how to deal with the extra variable of the cost of the stations being built as well. How should I approach this problem given the many variables? And how would I develop a recursive formula?
  Any help would be appreciated!</p>
  
  <p>EDIT: Yes I agree that the question is a bit unclear and also confused me at first, but that is all that was given in the question. I believe since the stations and pipelines all have different costs, there should be an optimal way of doing it.</p>