这道题的主要方法是写出前几项，然后找规律，发现可以使用DP记录之前的值来解答。它主要是为了找到能将原来的数整除的数字，然后通过这个数字找到现在这个数字的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int minSteps(int n) {
if(n==1) return 0;
if(n==2) return 2;
int* dp=new int[n+1];
dp[1]=0;
dp[2]=2;
for(int i=3;i<=n;i++){
dp[i]=i;
for(int j=2;j<i/2;j++){
if(i%j==0){
dp[i]=j+dp[i/j];
break;
}
}
}
return dp[n];
}
};
|