title: Robot coin collection - Dynamic Programming
body: <p><em>Robot Coin Collecting Problem</em></p>
  
  <blockquote>
    <p>Several coins are placed in cells of an <code>n × m</code> board, no more than
    one coin per cell. A robot, located in the upper left cell of the
    board, needs to collect as many of the coins as possible and bring
    them to the bottom right cell. On each step, the robot can move either
    one cell to the right or one cell down from its current location. When
    the robot visits a cell with a coin, it always picks up that coin.
    Design an algorithm to find the maximum number of coins the robot can
    collect and a path it needs to follow to do this.</p>
    
    <p>How would you modify the dynamic programming algorithm for the coin-
    collecting problem if some cells on the board are inaccessible for the
    robot? Apply your algorithm to the board below, where the inaccessible
    cells are shown by X’s. How many optimal paths are there for this
    board?</p>
    
    <p><a href="https://i.stack.imgur.com/ajsby.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/ajsby.png" alt="enter image description here"></a></p>
  </blockquote>
  
  <p>I coded for the above image, and it works well as the output shows 4. The inaccessible cell is marked as -1. However, I made <code>a[0][1]=1</code> accessible and I got a weird problem which shows <code>a[1][0]=3</code> after initialisation and the output is 6 instead of 5. How is the cell <code>a[1][0]</code> showing as 3 instead of being 1? Whatever I change at <code>a[0][1]</code> is getting affected at <code>a[1][0]</code>. How is that? Where am I going wrong?</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  
  int max(int a,int b) 
  {
      return a&gt;b?a:b;
  }
  
  int robot_coin_collect(int m,int n,int a[][n])
  {
      int i=1,j=1,k,c[m][n];
  
      c[0][0]=a[0][0];
      while(a[i][0]!=-1)
      {
          c[i][0]=c[i-1][0]+a[i][0];
          i=i+1;
      }
      for(;i&lt;m;i++)
          c[i][0]=-6;
      while(a[0][j]!=-1)
      {
          c[0][j]=c[0][j-1]+a[0][j];
          j=j+1;
      }
      for(;j&lt;n;j++)
          c[0][j]=-6;
  
      display(m,n,c);      // after initialising 
      printf("\n\n");
  
      for(i=1;i&lt;m;i++)
      {
           for(j=1;j&lt;n;j++)
           {
              if(a[i][j]!=-1)
                  c[i][j]=max(c[i-1][j],c[i][j-1])+a[i][j];
              else
                  c[i][j]=-6;
           }
      } 
  
      display(m,n,c);      // after the algorithm finishes, result
      return c[m-1][n-1];
  }
  
  void display(int m,int n,int c[][n])
  {
       int i,j;
  
       for(i=0;i&lt;m;i++)  
       {   
          for(j=0;j&lt;n;j++)
              printf("%d\t",c[i][j]);
          printf("\n");
      }
  }
  
  int main(void) 
  {
       int a[5][6]={0,1,0,1,0,0,
                   1,0,0,-1,1,0,
                   0,1,0,-1,1,0,
                   0,0,0,1,0,1,
                   -1,-1,-1,0,1,0};
  
       printf("%d",robot_coin_collect(5,6,a));
       return 0;
  }
  </code></pre>