문제 풀이 방식과 논리는 이해가 되는데, 시간 복잡도 계산이 이해가 안 되서요.
교재에 나와있는 코드의 시간복잡도가
부분 문제의 수 "O(ns)"에다, 각 부분 문제의 답을 계산하는데 드는 시간 "O(n)"을 곱한 "O(n^{2S)"입니다.}

여기서 부분 문제의 수가 왜 O(nS)가 되는 것인가요? ㅠㅠ
아래에 작성한 코드 있습니다.

//arr배열의 start인덱스에서 시작하는 크기 size의 수열에서 최소 오차 합 
int MinError(int start, int size)
{
    //부분 합
    //인덱스 오류 주의!
    int part;
    int part_z;

    if (start == 0)
    {
        part = partsum[start + size - 1];
        part_z = partsum_z[start + size - 1];
    }
    else
    {
        part= partsum[start + size - 1] - partsum[start - 1];
        part_z = partsum_z[start + size - 1] - partsum_z[start - 1];
    }


    int m = (int)(0.5 + (double)part / size);

    int result= part_z - 2 * m*part + m * m*size;

    return result;
}

int quantize(int start, int part)
{
    //양자화를 다 한 경우
    if (start == n)
        return 0;
    //숫자가 남았는데 더 이상 그룹을 지을 수 없는 경우
    if (part == 0)
        return MAX;
    if (cache[start][part] != 0)
        return cache[start][part];

    int *x = &cache[start][part];

    *x = MAX;

    for (int partsize = 1; start + partsize <= n; partsize++)
    {
        *x = min(*x, MinError(start, partsize) + quantize(start + partsize, part - 1));
    }

    return *x;
}