Martian Mining Problem of SPOJ

general
1

I am trying to solve the SPOJ Problem Martian Mining link text

but not able to think how to use Dynamic Programming here.

Please help me how to appply DP in this problem.

2

I’ll try not to give too much away.

Why are the following true?

  1. Every square should be mined (have some conveyor belt to a refinery)
  2. The length of conveyor belts will have an ordering

Focus on one direction (rows or columns) and play with small cases. Try n = 1 or 2.

Goodluck!