title: why the DP solutions are so closely linked..?why the solution is just totally opposite?
body: <p>The problem link is <a href="http://www.spoj.com/problems/AIBOHP/" rel="nofollow">Problem</a> . Although I am weak at DP I figured out a solution and got it acccepted but when I saw someone else's solution I was fascinated by  the closeness in the substructure...
  My solution code</p>
  
  <pre><code>void solve()
  {
  char str[6102];
  memset(dp,0,sizeof(dp));
  scanf(" %s",str+1);
  int i,j,k,l,n;
  n=strlen(&amp;str[1]);
  for(l=2;l&lt;=n;l++)
  {
      for(i=1;i&lt;=n-l+1;i++)
      {
          j=i+l-1;
          if(str[i]==str[j])
              dp[i][j]=dp[i+1][j-1];
          else
              dp[i][j]=min(dp[i+1][j]+1,dp[i][j-1]+1);
      }
  }
  printf("%d\n",dp[1][n]);
  }
  </code></pre>
  
  <p>But when I saw the solution online it was simply 
  answer=n - LCS( string, reversed string)</p>
  
  <p>And now comparing the substructure the +1 side comes on the opposite side i.e. </p>
  
  <pre><code>recurse(i,j)=recurse(i+1,j-1) {If string[i]==string[j]}
   else
  recurse(i,j)=min(recurse(i+1,j)+1,recurse(i,j-1)+1);
  </code></pre>
  
  <p>for my code and for LCS is here <a href="http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/" rel="nofollow">geeksforgeeks</a>(I think you obviously know this).. But I do not know why the solution is just totally opposite... in place of max--> min ... and that +1 part too(Comes with recurse(i,j-1)+1)..</p>