279-完全平方数

279-完全平方数

#include <iostream>
#include <vector>
#include <queue>

using namespace std;


class Solution {
public:
    int numSquares(int n) {
        int res = 0;
        if(n <= 0) return 0;

        queue< pair<int,int> > q;
        // 如果访问过了，就放弃第二次访问
        vector<bool> visited(n+1,false);
        q.push(make_pair(n,0));

        while(!q.empty()){
            int num = q.front().first;
            int step = q.front().second;
            q.pop();

            for(int i=0; ; i++){
                int a = num - i*i;
                if(a<0) break;
                if (a==0) return step+1;
                if (!visited[a]){
                    q.push( make_pair(a,step+1));
                    visited[a]=true;
                }
            }

        }

        return res;
    }
};

int main() {

    int res = Solution().numSquares(9);

    cout<<res<<endl;

    std::cout << "Hello, World!" << std::endl;
    return 0;
}

把这个问题转换为一个无权图找最短路径以后，因为有很多路径可以到达一个同一个节点(12–(1)–11–(4)–7、12–(4)–8--(1)–7)，比如12就可以通过两个路径同时到达7，这时我们只需要push到队列中一个7即可，

比如12，在第三层的时候，就可以从不同的路径到达7-2，如果不加限制的话，队列中就会推入两个7和2，这个冗余度会随着n的增大迅速增大，然后造成内存饱满

// 动态规划
/*这里使用动态规划来做。时间复杂度O(nlogn)，空间复杂度O(n)。代码非常精简 定义一个函数f(n)表示我们要求的解。f(n)的求解过程为： f(n) = 1 + min{ f(n-1^2), f(n-2^2), f(n-3^2), f(n-4^2), ... , f(n-k^2) } //(k为满足k^2<=n的最大的k) f(n) 存储了 组成完成n所需的最小完全平方数，f(1) = 1,f(2) = 2 ... f(5) = 2,f(6) = 3, */
int numSquares(int n) {
        int dp[n+1];
        memset(dp,0,n+1);
        for(int i=1; i<=n; i++){
            int minval = INT_MAX;
            for(int j =1; j*j<=i ;j++){
                minval = min(minval,dp[i-j*j]);
            }
            dp[i] = minval+1;
        }
        return dp[n];
    }