My simple dfs method C++


  • 5
    L
    class Solution {
    public:
        int numSquares(int n) {
           // int ret=INT_MAX;
            if(n==0)return 0;
            return  numSquares( n,1,INT_MAX); 
        }
        
        
         int numSquares(int n,int deep,int min) {
            if(deep>=min)return min;
            int sq=sqrt(n);
            if(sq*sq==n) { return 1;}
            for(int i=sq;i>=1;i--)
            {
                int temp=1+numSquares(n-i*i,deep+1,min);
                if( temp<min)min=temp;
            }
            return  min;
        }
    };

  • 0
    H

    if(deep>=min)return min; this is perfect; you are so smart;
    I think INT_MAX can change n


  • 0
    Z

    hard to explan.. what's the meaning of min in the function?
    it seems that it has mix meaning of min of curent min and total min,
    so I change it by seprate them by add current mi:

     int numSquares(int n,int deep,int min) {
        if(deep>=min)return min;
        int sq=sqrt(n);
        if(sq*sq==n) { return 1;}
        int mi = min-deep+1;
        for(int i=sq;i>=1;i--)
        {
            int temp=1+numSquares(n-i*i,deep+1,min);
            if( temp<mi)
            {
                mi=temp;
                min = deep + mi -1;
            }
        }
        return  mi;
    

  • 0
    T

    Nice!

    But his algorithm is not BFS, but actually DFS + pruning. The "deep" in the code denotes the current "cost", while "min" denotes the best solution found so far. Obviously, for those "search" which is absolutely worse than "min" with current cost "deep" could be discarded.


  • 0
    F

    Nice DFS solution, very well designed.


  • 0
    G

    My method is very similar to yours, but instead of search previous numSquares using "n - i * i", I try to jump as far as possible using "n % i * i". My method takes only 16ms.

    int numSquares(int n) {
        int squares = n;
        numSquares(n, 0, squares);
        return squares;
    }
    
    // Top down DP
    void numSquares(int n, int cnt, int& squares) {
        if (cnt >= squares) return;
        if (n == 0) {
            squares = min(squares, cnt);
            return;
        }
        for (int i = sqrt(n); i >= 1; --i) {           
            numSquares(n % (i * i), cnt + n / (i * i), squares);
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.