title: Minimum pluses required to make the equation (x = y) correct
body: <blockquote>
  <p><strong>Problem Statement</strong>:</p>
  <p>Given an equation “x=y”, for example, “111=12”, you need to add pluses
  inside x to make the equation correct. In our example “111=12”, we can
  add one plus “11+1=12” and the equation becomes correct. You need to
  find the minimum number of pluses to add to x to make the equation
  correct. If there is no answer print -1.</p>
  <p>Note that the value of y won’t exceed 5000. The numbers in the
  corrected equation may contain arbitrary amounts of leading zeros.</p>
  <p>Input Format The first line contains a string, A as described in the
  problem statement.</p>
  <p>Constraints 1 &lt;= len(A) &lt;= 10^3</p>
  </blockquote>
  <p>I tried the recursive approach. Which is for every character in the 'x', I have two options I can include the plus sign next to the current digit or move to the next digit (by including the current digit with the next digit) I checked all the combinations and found the minimum pluses. As you know, this is exponential in complexity. I'm not able to apply dynamic programming for this problem as I can't think of the states for the dynamic programming.</p>
  <p>I know this problem can be solved by dynamic programming. But, I don't know <strong>how to identify the state and the transition</strong>.</p>