[알고리즘]Dynamic Programming 알고리즘 작성하는거 좀 도와주십시오...

안녕하세요...

컴퓨터공학과 한 학생입니다...

알고리즘 과제를 받았는데 도저히 해결을 못하겠어서 조언이라도 얻으려고 이렇게 글을 올려봅니다..

각 cell은 맛의 정도를 표시한 -10 - 10 사이의 정수로 표시되어 있다. 여러분은 각 세로 줄의 한 부분을 잘라서 그 아랫부분을 모두 가져갈 수 있다. 이 작업은 가장 왼쪽 줄부터 오른쪽 줄로 한 칸씩 옮겨 가면서 하는데, 한 가지 주의할 것은 오른쪽 줄에서 잘린 높이는 왼쪽 줄의 높이보다 같거나 그 이상 이여야 한다.

5 8 2 4 -4 4
4 2 3 -3 -1 -6
2 -1 -7 6 -3 -8
-3 2 -8 -8 2 2
1 -5 3 9 3 -2

A B C D E F

위는 6줄 피자이다. 만일 A줄에서 밑에서부터 1+(-3)+2로 이루어진 3칸을 잘라서 가져갔다고 한다면 그 다음 B줄에서는 -5,2,1 을 잘라가거나 -5,2,1,7을 가져가거나 또는 모두 다인 -5,2,1,7,8을 가져가야 한다. 그 다음 C줄도 마찬 가지 규칙으로 가져가야 한다. 따라서 앞줄에서 욕심쟁이 마음으로 자르면 뒷줄에서 아주 손해를 볼 수 있다. 문제는 이렇게 했을 때 가장 맛있게 먹을 수 있는 방법을 (a) Dynamic Programming으로 구하는 알고리즘을 제시하고, (b) 위 그림에서 그 최대값을 계산하시오.

제가 지금까지 생각한 결과로는 F열부터 최대값을 구한 이후에 역순으로 최대값을 찾아나가는 방법을 시도해보고있었습니다..
하지만 경우의 수도 너무 많고 무식한 방법같아.. 조언 좀 해주시면 감사하겠습니다...