Initially on a notepad only one character 'A' is present. You can perform two operations on this notepad for each step:

1. Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).
2. Paste: You can paste the characters which are copied last time.

Given a number n. You have to get exactly n 'A' on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n 'A'.

Example 1:

Input: 3Output: 3Explanation:Intitally, we have one character 'A'.In step 1, we use Copy All operation.In step 2, we use Paste operation to get 'AA'.In step 3, we use Paste operation to get 'AAA'.

Note:

1. The n will be in the range [1, 1000].

想法：DP方式，状态转移表达时候result[i] = min(result[i],result[j]+i/j)

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