Recursive implementation of integer partition without re-arrangement

'use strict';

var sum = function(p, c) {
    return p + c;
};

var integerPartitionRec = function(n, k, S, divider_indexes) {
    if (divider_indexes === undefined) divider_indexes = [];
    if (i === 1) return [S[0], divider_indexes];
    if (k === 1) return [S.slice(0, n).reduce(sum), divider_indexes];

    var cost, prefix, min_cost = Number.MAX_VALUE,
        min_divider_indexes = [];
    for (var i = 1; i < n; i++) {
        prefix = integerPartitionRec(i, k - 1, S, divider_indexes.concat(i));
        cost = Math.max(prefix[0], S.slice(i, n).reduce(sum));
        if (cost < min_cost) {
            min_cost = cost;
            min_divider_indexes = prefix[1];
        }
    }

    return [min_cost, min_divider_indexes];
};

// define M[n,k] to be the minimum possible cost over all partitionings of {s1 , . . . , sn } 
// into k ranges, where the cost of a partition is the largest sum of elements in one of its parts. 
// O(kn^2) time

var integerPartitionDp = function(S, k) {
    var n = S.length;
    var cache = [
        [0]
    ];

    /* Dividers */
    var d = []

    /* Prefix Sums */
    var p = [0];

    for (var i = 1; i <= n; i++) {
        p[i] = p[i - 1] + S[i - 1];
    }

    for (i = 1; i <= n; i++) {
        cache[i] = [0, p[i]];
    }

    for (var j = 1; j <= k; j++) {
        cache[0][j] = 0
        cache[1][j] = S[0];
    }

    for (i = 2; i <= n; i++) {
        for (j = 2; j <= k; j++) {
            cache[i][j] = Number.MAX_VALUE;

            var cost;
            for (var x = 1; x < i; x++) {
                cost = Math.max(cache[x][j - 1], p[i] - p[x]);
                if (cost < cache[i][j]) {
                    cache[i][j] = cost;
                    if (d[i] === undefined) d[i] = [];
                    d[i][j] = x;
                }
            }
        }
    }

    var dividers = [];
    var curr = d[n][k];
    var count = k;
    while (curr !== undefined) {
      dividers.push(curr);
      curr = d[curr] ? d[curr][--count]: undefined;
    }

    return [cache[n][k], dividers];
}

var run = function() {
    var test = [1, 2, 3, 4, 5, 6, 7, 8, 9];
    console.log('S', test);

    console.log(integerPartitionRec(test.length, 3, test));
    console.log(integerPartitionDp(test, 3));
};

run();