leetcode解题: Perfect Squares (279)

发表于 | 分类于

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.

解法1：DP O(N^2) with O(N) 空间

如果用暴力的方法想：对于一个数字N，我们可以从1开始试， 因为1是一个perfect square,那么求出N - 1的解，假设为X，则N的解就是X+1
我们从1开始尝试所有可能的组合，然后求出了一系列的解之后挑选最小的值。但这样做的话复杂率特别高，应该是指数级的
实际上可以发现，这里有很多overlapping的问题，比如我们求12的最小值，那么如果第一个选择的值是4，则剩下的为8.
当我们在前面选择第一个值为2时，子问题变为寻找10 - 2 = 10的最小值，而当我们求10的最小值的时候可能已经求过了8的最小平方数。
所以我们可以想到用dp/memorization的方法去解决这个问题。

  1. 建立dp数组dp[N], N是要求的数字，dp数组中存储的是对应的这个数字n，他的最小平方和数。
  2. 初始化,将所有perfect square的数字都设为1
  3. 对于非perfect square的数字，dp[i] = Min(dp[j] + dp[i - j], j = 1 … i / 2),也就是说,dp[12] = Min of (dp[1] + dp[11], dp[2] + dp[10], …)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    public int numSquares(int n) {
        
        if (n < 0) {
            return 0;
        }
        
        if (n == 0 ) {
            return 1;
        }
        
        int[] dp = new int[n + 1];  
        for (int i = 1; i*i <= n; i++) {
            dp[i*i] = 1;
        }
        
        for (int i = 2; i <= n; i++) {
            if (dp[i] != 1) {
                int res = Integer.MAX_VALUE;
                for (int j = 1; j <= i/2; j++) {
                    int temp = dp[j] + dp[i - j];
                    res = Math.min(temp, res);
                }
                dp[i] = res;
            }
        }
        
        return dp[n];
    }