Dp solution like question 322 coin change


  • 0
    W
    class Solution {
    public:
        int numSquares(int n) {
            vector<int> num(n + 1, 0);
            int size = (int)sqrt(n);
            num[0] = 0;
            for(int i = 1; i <= n; i++)
            {
                int lmin = INT_MAX;
                for(int j = 1; j <= size; j++)
                {
                    if(i - j * j >= 0 && num[i - j * j] < lmin)
                        lmin = num[i - j * j];
                }
                num[i] = lmin + 1;
            }
            return num[n];
        }
    };

  • 0
    H

    Brute Force DFS solution in C ,Only 4ms!!!!!

     #define MAXN (0xffff + 1)
    #define INF (0x3fffffff)
    #define MAX_CNT (0xffffff)
    
    unsigned int square[MAXN]={0};
    int ans[MAX_CNT]={0};
    
    int count(int rest,int power)
    {
        if(rest < 4 || power < 2)
            return ans[rest]=rest;
        if(rest < MAX_CNT && ans[rest])
            return ans[rest];
        int ret = 20;
        for(int i= power; i > 0 ; i--)
        {
            int rst = rest % square[i];
            int tmp = rest / square[i];
            if(tmp >= ret)
                break;
            tmp += count(rst,sqrt(rst));
            if( tmp < ret)
                ret = tmp;
        }
        return ans[rest]=ret;
     }
    
    int numSquares(int n) {
        if(!square[1])
        {
            unsigned int idx = 1;
            for( ; idx < MAXN; idx ++)
                square[idx] = idx * idx;
        }
        return count(n,sqrt(n));
    }

Log in to reply
 

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