Readme

650.2-Keys-Keyboard

本题从题意上倾向于DP的解法。设计状态数组dp[n]表示恰好得到n个A的最小操作数。

我们思考dp[n]怎么得到。考虑到只有copy和paste两种模式，必然要求在得到n个A之前，纸面上必然是：有n/2个A，然后粘贴复制翻一番；或者有n/3个A，然后粘贴复制翻两番；或者依次类推，直面上有n/j个A，然后粘贴复制翻倍j-1次。所以这就得到了dp[n]的更新表达式。dp[n] = min(dp[n/j]+j) for j=2,3,...,n.

当然，如果采用贪心的策略可以优化上面的解。例如，我们要得到6个A，直觉上通过3个A翻一番的方法，要比通过2个A翻两番的方法更高效，更是会比通过1个A拷贝粘贴翻五番更高效。所以我们将j从小往大尝试，一旦遇到n/j整除的情况，就不再考虑其他j的可能性，取那样的j就能得到计算dp[n]的最优方案。

Leetcode Link