这道题目还是可以的。每个阶段有两种选择，求最短的决策次数。有好多种不同的做法，我们一个一个来。
方法1: BFS
把问题看成求无权重图中的最短路径，BFS可以找到最优解。
我们的节点有两个状态，当前的长度，剪贴板（上次复制后）的长度。
长度超过n一定无解，所以我们的状态最多只有n2种，每个状态最多拓展2个新的节点。
时间复杂度：O(n2)
空间复杂度：O(n2)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
class Solution { public: int minSteps(int n) { vector<vector<bool>> seen(n + 1, vector<bool>(n + 1)); queue<pair<int, int>> q; auto expand = [&](int len, int clip) { if (len > n || len > n || seen[len][clip]) return; q.emplace(len, clip); seen[len][clip] = true; }; int steps = 0; expand(1, 0); // init state. while (!q.empty()) { int size = q.size(); while (size--) { auto [len, clip] = q.front(); q.pop(); if (len == n) return steps; expand(len, len); // copy. expand(len + clip, clip); // paste. } ++steps; } return -1; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment