# Leetcode 650
###### tags: `LeetCode`
**solution 1 native DP (Dynamic Programming)**

public static int minSteps2(int n) {
int[] dp = new int[n + 1];
for (int k = 2; k <= n; k++) {
dp[k] = Integer.MAX_VALUE;
for (int i = 1; i < k; i++) {
if (k % i != 0) continue;
dp[k] = Math.min(dp[k], dp[i] + k / i);
}
}
return dp[n];
}
if you give n ,it will count and store the best route of 0-n in dp array
DP tips
1.A big question can be split to many small and same question
2.Store all of question result
3.Start from smallest question
4.DP is kind of 'BOTTOM UP' solution

**solution 2 non-DP - faster**

public static int minSteps(int n){
int res = 0;
for (int k = 2; k <= n; k++) {
for (; n % k == 0; res += k, n /= k);
}
return res;
}