LeetCode279. Perfect Squares（动态规划）

Medium
Accepted：169,699
Submissions：411,368

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

Example 1:

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

链接

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

题意

给定一个正整数n，找到构成它的最少完全平方数的数量。就是让最少的完全平方数加起来等于n。

题解

对于一个数n，存在等式$n = m + i * i$，同时对于m，存在等式 $m = p + j*j$，我们可以不停的把n、m、p分解为更小的完全平方数，在此过程中记录最少的分解方式。

设$dp[n]$表示构成数n的最少数量完全平方数，那么$dp[n] = min\{dp[n-i*i] + 1\}$，其中$i >= 1 \& n-i*i>0$。

平均时间复杂度$O(n\sqrt{n})$。

dp[0] = 0
dp[1] = dp[1] + 1 = 1
dp[2] = dp[1] + 1 = 2
dp[3] = dp[2] + 1 = 3
dp[4] = min{dp[4-1*1] + 1, dp[4-2*2] + 1} 
      = min{dp[3] + 1, dp[0] + 1}
      = min{4, 1}
      = 1
dp[5] = min{dp[5-1*1] + 1, dp[5-2*2] + 1} 
      = min{dp[4] + 1, dp[1] + 1}
      = min{2, 2}
      = 2
......
dp[n] = min{dp[n-i*i] + 1} i >= 1 & n-i*i > 0

代码

Runtime: 148 ms, faster than 30.79% of C++ online submissions for Perfect Squares.
Memory Usage: 11.3 MB, less than 49.24% of C++ online submissions for Perfect Squares.

class Solution {
public:
    int numSquares(int n) {
        vector <int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j * j <= i; ++j)
                dp[i] = min(dp[i - j*j] + 1, dp[i]);
        return dp[n];       
    }
};

The end.
2019年3月31日星期日