title: Optimal distance with dynamic programming
body: <p>Okay, so honestly this is a homework question, but I really did my best to find the solution, and I think I partially did.</p>
  
  <p>The question:</p>
  
  <p>We are given a series of cities whose positions are symbolized with only one coordinate and we are supposed to implement a given number of hospitals to cities so that the sum of each cities' distance to nearest hospital will be minimum.</p>
  
  <p>That is, if we are given the cities at 1, 3, 5, 7, 9, 11, 13 and if we are going to put 3 hospitals, the hospitals will be at 3, 7, 11 (actually there could be multiple best solutions for this one, did not check).</p>
  
  <p>We are advised to use dynamic programming and first check the case in which we implement only one hospital.</p>
  
  <p>I've figured out finding the subsequent hospital's location. I create a table, and of cities. Then to each cell, I put either the city of the current rows' distance to closest hospital that already build or city's distance to city of the corresponding column.</p>
  
  <p>For example, if we already implemented a hospital to 1, it would be like:</p>
  
  <p>*-1-3-5-7-9-11-13</p>
  
  <p>1|0|0|0|0|0|0||0|</p>
  
  <p>3|2|0|2|2|2|2|2|</p>
  
  <p>5|4|2|0|2|4|4|4|</p>
  
  <p>..............</p>
  
  <p>then sum the columns and find the next hospital.</p>
  
  <p>The problem is, I cannot figure out the first hospital that I'm supposed to build!!</p>
  
  <p>When I manually add one of the element of the actual solution, I can get the right answer so my partial solution should be true.</p>
  
  <p>BTW complexity should be O(CityNum^2), hospitalNum is a constant. So I can't use bruteforce.</p>
  
  <p>An example input and output (from the homework assg):</p>
  
  <p>Input:
  10 5 (10 is city num, 5 is hospital num)</p>
  
  <p>1 2 3 6 7 9 11 22 44 50 (coordinates)</p>
  
  <p>Output:</p>
  
  <p>9 (sum of minimum distances)</p>