This is the suggestion you've got in stackoverflow made more explicit:Define OPT(i,j,k,l,n) to be the maximum amount of coal you can get in $n$-steps with the condition that the last two packages that arrived to mine $X$ are i and j, and to mine $Y$ are k,l. Now, it is easy to compute OPT(i,j,k,l,n) using OPT(,,,,n-1) (just checking all the possibilities). You should be careful with the initial state (when there are less that 3 packages in some mine).

Thanks man! So now we know greedy fails. Thanks a lot again.

Two things:

1. I still don't get how to relate OPT(...,n-1) and OPT(...,n). Can you please give the recursion relation?

2. We just discovered that the order of sending the mines doesn't matter(!!). Like, if you solve the problem by rearranging the order of packages, you do get an optimal answer - at least it seems so for the problems we've tried.

For 2:

the order is realy important. Imagine your packages are AAABBBCCC, this is a lot worse than ABCABCABC.

The other question is hard to answer, you should "see" it. If don't you should try with an easier DP problem. Maybe if you try to compute a small example by hand (computing not only the final answer but also the table OPT) you will understand