原题链接在这里：

题目：

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题目. 

初始化 i 从2到n赋值 i 本身，代表每次直接paste 一个'A'. i = 1时, dp[i] = 0, 本身就有一个'A'.

状态转移，对于每一个j 在(1,n)区间内 如果i%j == 0 并且dp[j] + i/j比 dp[i]小就更新dp[i]. 表示重新 Copy All, 用1次操作, 再paste (i/j-1)次. 公用i/j-1+1 = i/j次操作. j不用减到1因为最开始的dp[i]就是通过1个'A'算出来的.

答案dp[n]. 

Time Complexity: O(n^2).

Space: O(n).

AC Java:

1 class Solution { 2     public int minSteps(int n) { 3         int [] dp = new int[n+1]; 4         for(int i = 2; i<=n; i++){ 5             dp[i] = i; 6             for(int j = i-1; j>1; j--){ 7                 if(i%j == 0){ 8                     dp[i] = Math.min(dp[i], dp[j]+i/j); 9                 }10             }11         }12         return dp[n];13     }14 }

类似.