Dynamic programming get maximum diamond

Question

I was trying to solve one Interview problem that is:

Given a matrix of n*n. Each cell contain 0, 1, -1. 0 denotes there is no diamond but there is a path. 1 denotes there is diamond at that location with a path -1 denotes that the path is blocked. Now you have start from 0,0 and reach to last cell & then return back to 0,0 collecting maximum no of diamonds. While going to last cell you can move only right and down. While returning back you can move only left and up.

I have solved the problem but I am not sure that is the optimal solution.What I am doing is

• That instead of going back from last cell to first cell I am allowing 2 iteration from initial cell to last cell.
• When I do first iteration I will try to obtain maximum number of diamonds using dynamic programming and after that I will remove those diamonds that are collected in first iteration from the matrix, ie: set matrix value 0 from 1.
• In second iteration I will call the same method as of first iteration but with modified matrix.
• And return the sum of both two calls.

Any suggestions about correctness? I have written the code, If that is needed I will share.

Answer 1

Your algorithm is not correct. Here is a counter example:

<table border="1">
  <tr>
    <td>1</td>
    <td>1</td>
    <td>1</td>
  </tr>
  <tr>
    <td>1</td>
    <td>1</td>
    <td>1</td>
  </tr>
   <tr>
    <td>0</td>
    <td>1</td>
    <td>1</td>
  </tr>
</table>

A maximum path from top to bottom will collect 5 diamonds and could be this:

<table border="1">
  <tr>
    <td>*</td>
    <td>*</td>
    <td>_</td>
  </tr>
  <tr>
    <td>_</td>
    <td>*</td>
    <td>*</td>
  </tr>
   <tr>
    <td>_</td>
    <td>_</td>
    <td>*</td>
  </tr>
</table>

But then your second iteration can only collect 2 more.

So your algorithm will return a max value of 7.

But there is a solution, with which you can collect 8.

E.g. if you path down looks like this:

<table border="1">
  <tr>
    <td>*</td>
    <td>_</td>
    <td>_</td>
  </tr>
  <tr>
    <td>*</td>
    <td>*</td>
    <td>_</td>
  </tr>
   <tr>
    <td>_</td>
    <td>*</td>
    <td>*</td>
  </tr>
</table>