function [boundaries,levels,totalerror] = dp(A,k,p);

% the error of the best solution for piecewise
% constant representation of A with k pieces

if (k<1) 
    best = NaN;
    boundaries = NaN;
    return
end

[m,n] = size(A);

    
for i=1:n
    lastpiece(1,i,1) = 1;
    for j=i:n
        cost(i,j,1) = Lperror(A(i:j),representative(A(i:j),p),p);
    end
end

for b=2:k
    for i=1:n
        cost(1,i,b) = cost(1,i,b-1);
        lastpiece(1,i,b) = -1;
        for j=1:i-1
            if cost(1,j,b-1)+cost(j+1,i,1)<=cost(1,i,b)
                cost(1,i,b) = cost(1,j,b-1)+cost(j+1,i,1);
                lastpiece(1,i,b) = j+1;
            end
        end
    end
end


totalerror = 0;
ind = n+1;
boundaries(k+1) = n;

while ind > 0 && k>0
    prevind = ind; 
    ind = lastpiece(1,ind-1,k);
    segmenterror = Lperror(A(ind:prevind-1),representative(A(ind:prevind-1),p),p);
    % [ind,prevind-1,mean(A(ind:prevind-1)),segmenterror];
    totalerror = totalerror + segmenterror;
    boundaries(k) = ind;
    levels(k) = representative(A(ind:prevind-1),p);
    k = k-1;
end


function [res] = representative(B,p);

if p==1
    res = median(B);
else
    res = mean(B);
end
