279. Perfect Squares

problem description

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.

algorithm thought

类似背包问题。这里是用空间为n的背包装载最少的物品。物品的体积就是正方形的面积。直接用动态规划解题。

解完之后，看discuss发现还有更加神奇的static动态规划。也就是利用static变量只会初始化一次的特点。能够利用之前的值。因为这个题的每次不同的n返回的值是不会变化的。求出n又相当于求出前面所有的值。所以这里可以用static保存前面已求出的值

code

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

algorithm analysis

本来算法的时间复杂度是O(n²)。但是用了static之后，整体时间从100ms级减到了4ms级