Perfect Squares

https://leetcode.com/problems/perfect-squares/description/

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

Thoughts

从一堆数1, 4, 9...中选取几个数使得和达到n，想到背包。由于是可以任取多次, 所以是完全背包. 让f[i][j]表示前i个元素能组成和为j的最短长度。这道题与之前的不同点一个在于是选取长度最短的，要用min，意味着有些数要初始化成MAX。还有一点也是比较tricky的点是状态转移方程是f[i][j - nums.get(i - 1)] ，而不是f[i - 1][j - nums.get(i - 1)] ，因为可以利用i来组成[j - nums.get(i-1)].

Code

class Solution {
    public int numSquares(int n) {
        List<Integer> nums = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            double pow = Math.pow(i, 2);
            if (pow > (double) n) {
                break;
            }
            nums.add((int)pow);
        }

        int m = nums.size();
        int[][] f = new int[m + 1][n + 1];
        for (int j = 1; j <= n; j++) {
            f[0][j] = Integer.MAX_VALUE; 
        }
        for (int i = 0; i <= m; i++) {
            f[i][0] = 0;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                f[i][j] = f[i - 1][j];
                if (j - nums.get(i - 1) >= 0) {
                    f[i][j] = Math.min(f[i][j], f[i][j - nums.get(i - 1)] + 1);                  
                }
                //System.out.println(i + "," + j + ": " + f[i][j]);
            }
        }

        return f[m][n];
    }
}

Analysis

Errors:

1. f[i][j - nums.get(i - 1)]后面忘了+1.

2. f[i][j - nums.get(i - 1)]写成了[f[i - 1][j - nums.get(i - 1)]

时间复杂度为O(mn).

Ver.2

class Solution {
    public int numSquares(int n) {
        List<Integer> nums = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            double pow = Math.pow(i, 2);
            if (pow > (double) n) {
                break;
            }
            nums.add((int)pow);
        }

        int m = nums.size();
        int[] f = new int[n + 1];

        f[0] = 0;
        for (int i = 1; i <= n; i++) {
            f[i] = Integer.MAX_VALUE;
        }

        for (int i = 0; i < m; i++) {
            for (int j = nums.get(i); j <= n; j++) {
                if (f[j - nums.get(i)] != Integer.MAX_VALUE) {
                    f[j] = Math.min(f[j], f[j - nums.get(i)] + 1);                  
                }
                //System.out.println(i + "," + j + ": " + f[i][j]);
            }
        }

        return f[n];
    }
}