function pix = findSeam_Dyn_sol(energy)

%M is the cumulative energy function
M = zeros(size(energy));
%Prev_indices is a matrix that will point to the element in the (i-1)th row
%that an M(i,j) came from.
prev_indices = zeros(size(M));
M(1,:) = energy(1,:);

for i = 2:size(energy,1)
   %for columns not on the extreme right or left
   for j = 2:size(energy,2)-1
       [min_M,col_idx] = min( [M(i-1,j-1),M(i-1,j),M(i-1,j+1)] );
       prev_indices(i,j) = j+ (col_idx-2);
       M(i,j) = energy(i,j) +  min_M;
   end 
   %for the right edge
   j = size(energy,2);
   [min_M,col_idx] = min([M(i-1,j-1),M(i-1,j)]);
   prev_indices(i,j) = j+ (col_idx-2);
   M(i,j) = energy(i,j) +  min_M;
   
   %for the left edge
   j = 1;
   [min_M,col_idx] = min([M(i-1,j),M(i-1,j+1)]);
   prev_indices(i,j) = j+ (col_idx-1);
   M(i,j) = energy(i,j) +  min_M;
end

%find the ending location of the path that contains the least energy
[min_M, col_idx] = min(M(end,:));

%re-trace the path 
pix = zeros(size(M,1),1);

pix(end) = col_idx;
for i = length(pix)-1:-1:1     
    pix(i) = prev_indices(i+1,pix(i+1));
end
    
    
    
    
    
    
    
    
    
    
%     
%     
% Pot=energy;
% 
% for ii=2:size(Pot,1)
%     pp=Pot(ii-1,:);
%     ix=pp(1:end-1)<pp(2:end);
%     pp([false ix])=pp(ix);
%     ix=pp(2:end)<pp(1:end-1);
%     pp(ix)=pp([false ix]);
%     Pot(ii,:)=Pot(ii,:)+pp;
% end
% 
% %Walk down hill
% pix=zeros(size(energy,1),1);
% [mn,pix(end)]=min(Pot(end,:));
% pp=find(Pot(end,:)==mn);
% pix(end)=pp(ceil(rand*length(pp)));
% 
% for ii=size(energy,1)-1:-1:1
%     [mn,gg]=min(Pot(ii,max(pix(ii+1)-1,1):min(pix(ii+1)+1,end)));
%     pix(ii)=gg+pix(ii+1)-1-(pix(ii+1)>1);
% end