# 0650. 2 Keys Keyboard
###### tags: `Leetcode` `Medium` `Dynamic Programming` `Greedy`
Link: https://leetcode.com/problems/2-keys-keyboard/
## 思路
比较容易想到的方法就是```dp```

他们可以由前面的```i/2```个A paste1次 copy1次; 也可以由前面的```i/3```个A paste1次 copy2次...
所以我们要找到所有可能的```j``` ```i%j==0``` 这样```i```个A就可以通过```i/j```个A 再加上1次paste ```j-1```次copy得到
因此```dp[i] = Math.min(dp[i], dp[i/j]+j)```

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

class Solution {
public int minSteps(int n) {
int[] dp = new int[n+1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[1] = 0;
for(int i=2; i<=n; i++){
for(int j=2; j<=i; j++){
if(i%j==0){
dp[i] = Math.min(dp[i/j]+j, dp[i]);
break;
}
}
}
return dp[n];
}
}

c++

class Solution {
public:
int minSteps(int n) {
auto dp = vector<int>(n+1, INT_MAX);
dp[1] = 0;
for(int i=2; i<=n; i++){
for(int j=i-1; j>=1; j--){
if(i%j==0){
dp[i] = min(dp[i], dp[j]+1+i/j-1);
break;
}
}
}
return dp[n];
}
};