---
# System prepended metadata

title: 0650. 2 Keys Keyboard
tags: [Leetcode, Dynamic Programming, Medium, Greedy]

---

# 0650. 2 Keys Keyboard
###### tags: `Leetcode` `Medium` `Dynamic Programming` `Greedy`
Link: https://leetcode.com/problems/2-keys-keyboard/
## 思路
比较容易想到的方法就是```dp```
```dp[i]```表示最少需要几步就会有```i```个A
他们可以由前面的```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
```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++
```cpp=
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];
    }
};
```