/*

For example, with strings source = "ABCDEFG"
target = "ABDFFGH" we might return:
["A", "B", "-C", "D", "-E", "F", "+F", "G", "+H"]

.
CCCACDC
BCCBCDC
.

// add + remove + 3 operations
// add + keeping + remove + 2 operations

// if we are at position i, and we will use the letter in position i+x
// we will have X add operations + keeping

//


// if the current letter is not in the next letters of the target
// you should remove

-A B +B C D C // 6 operations

// removing
-A B -C -D -C +B +C +D +C // 9 operations

// adding
also not optimal

input: str source | str target
return: array of operations in the form [-+]?[A-Z]

/////////////////////////

approach number 2:

        .
source: CDEFG
target: DFFGH
        .

recursive function(int positionInSource, int positionInTarget) {
  sourceLetter = source[positionInSource]
  targetLetter = target[positionInTarget]

  if (targetLetter == sourceLetter) {
    cost = 1
    cost += function(positionInSource+1, positionInTarget+1)
    return
  }

  // here they are different

  costRemove = 1 // -Letter
  costRemove += function(positionInSource+1, positionInTarget)

  costAdd = 1
  costAdd += function(positionSource, positionInTarget+1)

  return min(costRemove, costAdd)
}

*/

int solve(int srcIndex, int tgtIndex, const string& source, const string& target, vector<vector<int>>& dp) {
  if (dp[srcIndex][tgtIndex] != -1) {
    return dp[srcIndex][tgtIndex];
  }

  if (tgtIndex >= target.size() && srcIndex >= source.size()) {

  }
  if (tgtIndex >= target.size()) {
    int costToRemove = 1 + solve(srcIndex + 1, tgtIndex, source, target, dp);
    dp[srcIndex][tgtIndex] = costToRemove;
    return costToRemove;
  }
  if (srcIndex >= source.size()) {
    int costToAdd = 1 + solve(srcIndex, tgtIndex + 1, source, target, dp);
    dp[srcIndex][tgtIndex] = costToAdd;
    return costToAdd;
  }

  char srcLetter = source[srcIndex];
  char tgtLetter = target[tgtIndex];

  if (srcLetter == tgtLetter) {
    int cost = 1;
    cost += solve(srcIndex + 1, tgtIndex + 1, source, target, dp);
    dp[srcIndex][tgtIndex] = cost;
    return cost;
  }

  int costToRemove = 1 + solve(srcIndex + 1, tgtIndex, source, target, dp);
  int costToAdd = 1 + solve(srcIndex, tgtIndex + 1, source, target, dp);

  int minimalCost = min(costToRemove, costToAdd);
  dp[srcIndex][tgtIndex] = minimalCost;
  return minimalCost;
}

vector<string> getMoves(string source, string target) {
  vector<string> answer;
  vector<vector<int>> dp;

  for (int i = 0; i < source.size(); i++) {
    dp[i] = vector<int>(target.size(), -1);
  }

  solve(0, 0, source, target, dp);

  int minimalCost = dp[0][0];

  pair<int,int> nextPos = dpPos[0][0];

  return answer;
}

//
*


B


1+ -1 -1
-1 -1 -1
-1 -1 -1

(1,1) (x,x) (x,x)
(x,x) (2,1) (x,x)
(x,x) (2,2) (-1,-1)

*//