Leetcode 650: 2 Keys Keyboard

 https://leetcode.com/problems/2-keys-keyboard/description/

Notes:

This question is a weaker version of Leetcode 651 (4 Keys Keyboard), but the idea is similar: 

      if we have solved the same question with a smaller n, then we should think about how to use the calculated results directly.

Let say we have solved all the smaller dp's with a smaller indexes than i, now we want to calculate dp[i].

Here dp[i] means the minimum number of steps to get n 'A's.

If we have dp[j], and i%j == 0, then one way to get dp[i] is: dp[j] + i/j. Why?

We just simply Ctr-C once on j 'A's, then (Ctr-V i/j  - 1) times. So the overall is dp[j] + i/j.

if(i%j != 0) then we cannot get i 'A's from j 'A'  (I will leave this to you to prove...)

Now the question becomes clear: we just need to go though all the smaller ones (which has been calculated at this moment), then find the smallest value.

There is maybe a even faster way to do this, keep tuned.

See the code below:

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