Perfect Squares Solutions in C++

// Source : https://leetcode.com/problems/perfect-squares/
// Author : Hao Chen
// Date   : 2015-10-25




class Solution {
public:

    int numSquares(int n) {
        return numSquares_dp_opt(n); //12ms
        return numSquares_dp(n); //232ms
    }
    
    /*
     * Dynamic Programming
     * ===================
     *   dp[0] = 0 
     *   dp[1] = dp[0]+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 } 
     *         = 1               
     *   dp[5] = min{ dp[5-1*1]+1, dp[5-2*2]+1 } 
     *         = min{ dp[4]+1, dp[1]+1 } 
     *         = 2
     *   dp[6] = min{ dp[6-1*1]+1, dp[6-2*2]+1 } 
     *         = min{ dp[5]+1, dp[2]+1 } 
     *         = 3
     *   dp[7] = min{ dp[7-1*1]+1, dp[7-2*2]+1 } 
     *         = min{ dp[6]+1, dp[3]+1 } 
     *         = 4
     *   dp[8] = min{ dp[8-1*1]+1, dp[8-2*2]+1 } 
     *         = min{ dp[7]+1, dp[4]+1 } 
     *         = 2
     *   dp[9] = min{ dp[9-1*1]+1, dp[9-2*2]+1, dp[9-3*3] } 
     *         = min{ dp[8]+1, dp[5]+1, dp[0]+1 } 
     *         = 1
     *   dp[10] = min{ dp[10-1*1]+1, dp[10-2*2]+1, dp[10-3*3] } 
     *          = min{ dp[9]+1, dp[6]+1, dp[1]+1 } 
     *          = 2
     *                           ....
     *
     *   So, the dynamic programm formula is
     *   
     *      dp[n] = min{ dp[n - i*i] + 1 },  n - i*i >=0 && i >= 1
     *
     */
    int numSquares_dp(int n) {
        if ( n <=0 ) return 0;
        
        int *dp = new int[n+1];
        dp[0] = 0;
        
        for (int i=1; i<=n; i++ ) {
            int m = n;
            for (int j=1; i-j*j >= 0; j++) {
                m = min (m, dp[i-j*j] + 1);
            }
            dp[i] = m;
        }
    
        return dp[n];
        delete [] dp;
    }
    
    //using cache to optimize the dp algorithm
    int numSquares_dp_opt(int n) {
        if ( n <=0 ) return 0;
        
        static vector<int> dp(1, 0);
        if (dp.size() >= (n+1) ) return dp[n];
        
        for (int i=dp.size(); i<=n; i++ ) {
            int m = n;
            for (int j=1; i-j*j >= 0; j++) {
                m = min (m, dp[i-j*j] + 1);
            }
            dp.push_back(m);
        }
    
        return dp[n];
    }
};

/// Source : https://leetcode.com/problems/perfect-squares/description/
/// Author : liuyubobobo
/// Time   : 2017-11-17

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

using namespace std;

/// BFS
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    int numSquares(int n) {

        if(n == 0)
            return 0;

        queue<pair<int, int>> q;
        q.push(make_pair(n, 0));

        vector<bool> visited(n + 1, false);
        visited[n] = true;

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

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

        throw invalid_argument("No Solution.");
    }
};

int main() {

    cout << Solution().numSquares(12) << endl;
    cout << Solution().numSquares(13) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/perfect-squares/description/
/// Author : liuyubobobo
/// Time   : 2017-11-17

#include <iostream>
#include <vector>

using namespace std;

/// Memory Search
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {

public:
    int numSquares(int n) {

        vector<int> mem(n + 1, -1);

        return numSquares(n, mem);
    }

private:
    int numSquares(int n, vector<int>& mem){

        if(n == 0)
            return 0;

        if(mem[n] != -1)
            return mem[n];

        int res = INT_MAX;
        for(int i = 1; n - i * i >= 0; i ++ )
            res = min(res, 1 + numSquares(n - i * i, mem));
        return mem[n] = res;
    }
};

int main() {

    cout << Solution().numSquares(12) << endl;
    cout << Solution().numSquares(13) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/perfect-squares/description/
/// Author : liuyubobobo
/// Time   : 2017-11-17

#include <iostream>
#include <vector>

using namespace std;

/// Dynamic Programming
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {

public:
    int numSquares(int n) {

        vector<int> mem(n + 1, INT_MAX);
        mem[0] = 0;
        for(int i = 1; i <= n ; i ++)
            for(int j = 1 ; i - j * j >= 0 ; j ++)
                mem[i] = min(mem[i], 1 + mem[i - j * j]);

        return mem[n];
    }
};

int main() {

    cout << Solution().numSquares(12) << endl;
    cout << Solution().numSquares(13) << endl;

    return 0;
}