LC: 4 Keys Keyboard - spiralgo/algorithms GitHub Wiki

4 Keys Keyboard

The Essence:

There are a few points to understand: The Ctrl+A and Ctrl+C operations are always done together. In some cases, pasting twice is more efficient than copying twice and pasting with that. If pasting twice is possible, then pasting 3, 4 or 5 times is also possible. Then there must be a way of building up the solution by using the solutions to previous costs and trying them with the multiplication counts.

Details:

For example, to paste 5 times, one can multiply this with the value of the pastes 6 steps ago. This naturally corresponds to dynamic programming. At each step, the maximum among paste counts needs to be found.

Eventually, all the pastes converge into being the most optimum at 4 pastes.

More rigorous explanation of this and the code can be found at: https://github.com/spiralgo/algorithms/pull/301