[C++] Simple DP; 4 ms; explains why Hint 2 is suboptimal
From the problem description:\n\n> [Hint 1] Use dynamic programming.\n\nHint 1 is good. \uD83D\uDC4D Dynamic programming makes sense here.\n\n> [Hint 2] dp[i][j
From the problem description:\n\n> **[Hint 1]** Use dynamic programming.\n\nHint 1 is good. \uD83D\uDC4D Dynamic programming makes sense here.\n\n> **[Hint 2]** dp[i][j][k]: smallest movements when you have one finger on i-th char and the other one on j-th char already having written k first characters from word.\n\nHint 2 points to a reasonable first approach to the problem, but one yielding a suboptimal solution. Since it is never helpful to move the same finger twice in a row without typing anything, we can assume that the previous key that was pressed always has a finger positioned over it. So `dp[i][j][k]` has a redundant element. `dp[i][j]` should be enough because `k` can be deduced from `i`. This reduces both time and space complexity by an order of magnitude.\n\nNote that this approach doesn\'t consider a "left finger" and "right finger", but rather a "finger that just typed" and an "other finger". It doesn\'t matter which is which.\n\nFinally, we don\'t need to keep the whole 2D array stored at all times, since the algorithm only ever refers back to the previous row. So that reduces our space complexity by another order of magnitude, leaving us with:\n\nTime complexity: **O(\u03B1\xB7N)**\nSpace complexity: **O(\u03B1)**\n\nwhere **\u03B1** is the size of the alphabet (in this case \u03B1 = 26) and **N** is the size of the word.\n\n```C++\nint distance(int a, int b) {\n  /* Manhattan distance on a keyboard with 6 columns */\n  return abs(a/6 - b/6) + abs(a%6 - b%6);\n}\n\nint minimumDistance(string w) {\n  int const N = w.size();\n\n  /* Convert all letters in the word to the values 0..25 */\n  for (char& c : w)\n    c -= \'A\';\n\n  /* Dynamic programming */\n  int dp[2][26] = {0}; // (index of prev char typed % 2) \u2192 (position of other finger) \u2192 (cost to type the rest)\n\n  for (int i = N-2; i >= 0; --i)\n    for (int j = 0; j < 26; ++j)\n      dp[i%2][j] = min(\n        distance(w[i], w[i+1]) + dp[(i+1)%2][j   ], // moving the finger that just typed\n        distance(j,    w[i+1]) + dp[(i+1)%2][w[i]]  // moving the other finger\n      );\n\n  /* We assume that the first character is free to type, and leaves one finger on that key.\n     But we do still need to pick the optimal position for the other finger. */\n  return *min_element(dp[0], dp[0]+26);\n}\n```
['Dynamic Programming', 'C']