title: How to understand the dynamic programming solution in linear partitioning?
body: <p>I'm struggling to understand the dynamic programming solution to linear partitioning problem. I am reading the The <a href="http://www.algorist.com/" rel="nofollow noreferrer">Algorithm Design Manual</a> and the problem is described in section 8.5.  I've read the section countless times but I'm just not getting it. I think it's a poor explanation (the what I've read up to now has been much better), but I've not been able to understand the problem well enough to look for an alternative explanation. Links to better explanations welcome!</p>
  <p>I've found a page with text similar to the book (maybe from the first edition of the book): <a href="http://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/BOOK2/NODE45.HTM" rel="nofollow noreferrer">The Partition Problem</a>.</p>
  <p>First question: In the example in the book the partitions are ordered from smallest to largest. Is this just coincidence? From what I can see the ordering of the elements is not significant to the algorithm.</p>
  <p>This is my understanding of the recursion:</p>
  <p>Lets use the following sequence and partition it into 4:</p>
  <pre><code>{S1...Sn} =  100   150   200   250   300   350   400   450   500
  k = 4
  </code></pre>
  <p>Second question: Here's how I think the recursion will begin - have I understood it correctly?</p>
  <p>The 1st recursion is:</p>
  <pre><code>100   150   200   250   300   350   400   450 | 500 //3 partition to go
  100   150   200   250   300   350   400 | 450 | 500 //2 partition to go 
  100   150   200   250   300   350 | 400 | 450 | 500 //1 partition to go
  100   150   200   250   300 | 350 | 400 | 450 | 500 //done
  </code></pre>
  <p>The 2nd recursion is:</p>
  <pre><code>100   150   200   250   300   350   400   450 | 500 //3 partition to go
  100   150   200   250   300   350   400 | 450 | 500 //2 partition to go 
  100   150   200   250   300   350 | 400 | 450 | 500 //1 partition to go
  100   150   200   250 | 300   350 | 400 | 450 | 500 //done
  </code></pre>
  <p>The 3rd recursion is:</p>
  <pre><code>100   150   200   250   300   350   400   450 | 500 //3 partition to go
  100   150   200   250   300   350   400 | 450 | 500 //2 partition to go 
  100   150   200   250   300   350 | 400 | 450 | 500 //1 partition to go
  100   150   200 | 250   300   350 | 400 | 450 | 500 //done
  </code></pre>
  <p>The 4th recursion is:</p>
  <pre><code>100   150   200   250   300   350   400   450 | 500 //3 partition to go
  100   150   200   250   300   350   400 | 450 | 500 //2 partition to go 
  100   150   200   250   300   350 | 400 | 450 | 500 //1 partition to go
  100   150 | 200   250   300   350 | 400 | 450 | 500 //done
  </code></pre>
  <p>The 5th recursion is:</p>
  <pre><code>100   150   200   250   300   350   400   450 | 500 //3 partition to go
  100   150   200   250   300   350   400 | 450 | 500 //2 partition to go 
  100   150   200   250   300   350 | 400 | 450 | 500 //1 partition to go
  100 | 150   200   250   300   350 | 400 | 450 | 500 //done
  </code></pre>
  <p>The 6th recursion is:</p>
  <pre><code>100   150   200   250   300   350   400   450 | 500 //3 partition to go
  100   150   200   250   300   350   400 | 450 | 500 //2 partition to go 
  100   150   200   250   300 | 350   400 | 450 | 500 //1 partition to go
  100   150   200   250 | 300 | 350   400 | 450 | 500 //done
  </code></pre>
  <p>The 7th recursion is:</p>
  <pre><code>100   150   200   250   300   350   400   450 | 500 //3 partition to go
  100   150   200   250   300   350   400 | 450 | 500 //2 partition to go 
  100   150   200   250   300 | 350   400 | 450 | 500 //1 partition to go
  100   150   200 | 250   300 | 350   400 | 450 | 500 //done
  </code></pre>
  <p>The 8th recursion is:</p>
  <pre><code>100   150   200   250   300   350   400   450 | 500 //3 partition to go
  100   150   200   250   300   350   400 | 450 | 500 //2 partition to go 
  100   150   200   250   300 | 350   400 | 450 | 500 //1 partition to go
  100   150 | 200   250   300 | 350   400 | 450 | 500 //done
  </code></pre>
  <p>The 9th recursion is:</p>
  <pre><code>100   150   200   250   300   350   400   450 | 500 //3 partition to go
  100   150   200   250   300   350   400 | 450 | 500 //2 partition to go 
  100   150   200   250   300 | 350   400 | 450 | 500 //1 partition to go
  100 | 150   200   250   300 | 350   400 | 450 | 500 //done
  </code></pre>
  <p>etc...</p>
  <p>Here's the code as it appears in the book:</p>
  <pre class="lang-cpp prettyprint-override"><code>partition(int s[], int n, int k)
  {
      int m[MAXN+1][MAXK+1];                  /* DP table for values */
      int d[MAXN+1][MAXK+1];                  /* DP table for dividers */ 
      int p[MAXN+1];                          /* prefix sums array */
      int cost;                               /* test split cost */
      int i,j,x;                              /* counters */
      
      p[0] = 0;                               /* construct prefix sums */
      for (i=1; i&lt;=n; i++) p[i]=p[i-1]+s[i];
      
      for (i=1; i&lt;=n; i++) m[i][3] = p[i];    /* initialize boundaries */
      for (j=1; j&lt;=k; j++) m[1][j] = s[1];
      
      
      for (i=2; i&lt;=n; i++)                    /* evaluate main recurrence */
          for (j=2; j&lt;=k; j++) {
              m[i][j] = MAXINT;
              for (x=1; x&lt;=(i-1); x++) {
                  cost = max(m[x][j-1], p[i]-p[x]);
                  if (m[i][j] &gt; cost) {
                      m[i][j] = cost;
                      d[i][j] = x;
                  }
              }
          }
  
      reconstruct_partition(s,d,n,k);         /* print book partition */
  }
  </code></pre>
  <p>Question about the algorithm:</p>
  <ol>
  <li>What values are being stored in the <code>m</code> and <code>d</code>?</li>
  <li>What does 'cost' mean? Is it simply the total of the elements values within a partition? Or is there some additional more subtle meaning?</li>
  </ol>