Topcoder SRM 612 DIV 2 L2 EmoticonsDiv2

// Topcoder SRM 612 DIV 2 L2 EmoticonsDiv2

import java.util.*;
import java.math.*;

//rename the class name before submitting
public class EmoticonsDiv2 {
public static void main(String[] args) {
EmoticonsDiv2 obj = new EmoticonsDiv2();
System.out
.println(
obj.printSmiles(
1000
));
}

public int printSmiles(int smiles) {
int[][] dp = new int[1001][1001];
int[] minSecs = new int[1001];
for (int i = 0; i < 1001; i++) {
minSecs[i] = Integer.MAX_VALUE;
}
for (int i = 0; i < 1001; i++) {
for (int j = 0; j < 1001; j++) {
dp[i][j] = -1;
}
}
dp[1][2] = 2;
minSecs[1] = 2;
for (int j = 2; j < 1001; j++) {
dp[1][j] = j;
minSecs[j] = j;
}
for (int i = 2; i < 1001; i++) {
for (int j = i; j < 1001; j += i) {
if (j == i) {
dp[i][j] = minSecs[j] + 1;
}
else {
dp[i][j] = dp[i][j - i] + 1;
}
minSecs[j] = Math.min(minSecs[j], dp[i][j]);
}
}

return minSecs[smiles];
}
}