650.Two Keys Keyboard（M）

题目描述

最初给你一个字母A，你每一步能进行两种操作：
1. 对当前所有字母进行复制
2. 粘贴之前最后一次复制的字母到当前字符串的尾部
给定一个字符串的长度n，求解最小使得字符串长度变为n的步数，下图是题中的一个例子

刚开始读完题意，一下就想到可以用宽度优先搜索来解这道题，因为每一步有两种选择，相当于这是一颗二叉树，你要找到最靠近根的目标节点，所以可以用BFS完成。写完之后，发现果然内存超出了限制，这也没办法，这是BFS最大的缺点之一。于是尝试着使用A*算法来减少节点的个数，我将问题松弛为后，得到一个估值函数是当前步数+（目标个数-当前字符串个数）/当前复制的个数，结果超时，很难受。始终没有解决的方案，想用贪婪算法，但没想到一个合理的贪婪方式，于是打开了答案

这是我觉得最新手不友好型的答案。这里我来介绍一下，答案为什么是这样的。

求解一个动态规划问题，需要把问题分解为一个一个的子问题，那么这道题应该怎么分解呢？由观察可以知道，如果一个数k = a * b（a,b不等于1, b为k的最小公约数），当k>= 4时，k>=a + b，k可以由a粘贴b-1次得到，b-1次肯定是小于k次的（k次是有由1个字母直接粘贴到k个字母，中途不进行任何的复制操作），所以现在问题变成，我们要求解得到a的最小步数。现在，我们假定n = x * y，y = q * w，且x为n的最小公因数，那么n >= x + y >= x + q + w。这样就把问题分解成了f(n) = x + f(n/x)，把大问题变成了一个更小的问题，我们每次只需要找到一个x，一个无法再被拆分的x。当无法再分解时，便是需要求得的最优解。
一个动态规划问题最困难的便是发现这些规律了，需要多练习这类题，才能加强这方面的短板。