<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Partition Problem
Eric Ren
Notes from Skiena, 2008.
Recurrence Relation
Let's start with the recurrence relation.  Here is the math
Step1:  Less imperative
<ASSISTANT_TASK:>
Python Code:
# To better match the math equations above, collection starts at index 1 instead of 0
def partition(collection, n, k):
    if n == 0:
        return "No elements in collection to partition"
    
    
    # initialize matrix
    m = [[float('inf')] * k for _ in range(n+1)]
    d = [[-1] * k for _ in range(n+1)]
    
    # create prefix sums
    prefix_sum = [0] * (n+1)
    for i in range(1, n+1):
        prefix_sum[i] = prefix_sum[i-1] + collection[i]    
    
    # Base case from eq (1) above
    for i in range(1, n+1):
        m[1][i] = collection[1]
    
    # Base case from eq (2) above
    for i in range(1, n+1):
        m[i][1] = prefix_sum[i]
        
    
    # eq 0
    for i in range(2, n+1):
        for j in range(2, k+1):
            for x in range(1, i):
                cost = max(m[x][j-1].cost, prefix_sum[i]-prefix_sum[x])
                if m[i][j] > cost:
                    m[i][j] = cost
                    d[i][j] = x
                    
                    
          
    reconstruct_partition(collection, d, n, k)
    
    
def reconstruct_partition(collection, dividers, n, k):
    
    
    
    
def print_items(collection, start, end):
    
                    
        
    
    
Explanation: Partition Problem
Eric Ren
Notes from Skiena, 2008.
Recurrence Relation
Let's start with the recurrence relation.  Here is the math:
$$S = [s_1, s_1,..., s_n], s \in \mathbb{R} $$
\begin{align} 
P(n, k) & = \min_{i=1}^{n} \max( P(i, k-1), \sum_{j=i+1}^n s_j ) \tag{0} \
P(1, k) & = s_1  \tag{1} \
P(n, 1) & = \sum_{i=1}^{n} s_i  \tag{2} 
\end{align}
Unfortunately Python does not support pattern matching. Else we can write very idiomatic code that will look just like the recurrence above.
Now on to the different approaches:
Recursive
Recursive w/ Memoization
Imperative
End of explanation
def partition()
Explanation: Less imperative
End of explanation
<END_TASK>