279.Perfect Squares

Posted on | In

Solution 1: accepted 48ms

  1. Base case: dp[0] = 0;
  2. Induction rule:
    dp[i] = min(dp[i - j j] + 1) where j j <= i
    dp[1] = dp[0] + 1 = 1;
    dp[2] = dp[1] + 1 = 2;
    dp[3] = dp[3] + 1 = 3;
    dp[4] = min(dp[4-11=3] + 1, dp[4-22=0] + 1) = 1; 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int numSquares(int n) {
    int[] dp = new int[n + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        int j = 1; 
        while (j * j <= i) {
            dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            j++;
        }
    }
    return dp[n];
}