2024-08-19
650. 2 Keys Keyboard
There is only one character 'A' on the screen of a notepad. You can perform
one of two operations on this notepad for each step:
Copy All: You can copy all the characters present on the screen (a
partial copy is not allowed).
Paste: You can paste the characters which are copied last time.
Given an integer n, return the minimum number of operations to get the
character 'A' exactly n times on the screen.
泥板大師不是用DP就是數學姊
只剩我只會暴力解了
反正就是從1開始貼到n
中間如果發現多複製一次比較快就多複製一次
class Solution {
public:
int minSteps(int n) {
if (n < 2) {
return 0;
}
int curMaxNum = n;
int curOpNum = 1;
int curScreen = 1;
int curCopied = 1;
while (curScreen < (n / 2 + 1)) {
if ((n - curScreen) % curScreen == 0) {
if ((n - curScreen) / curScreen + curOpNum + 1 < curMaxNum) {
curMaxNum = (n - curScreen) / curScreen + curOpNum + 1;
curOpNum++;
curCopied = curScreen;
}
}
curOpNum++;
curScreen += curCopied;
}
return curMaxNum;
}
};