convert it to complete knapsack


  • 0
    S

    complete knapsack

    class Solution {
    public:
        int numSquares(int n) {
            int num = 1;
            while(num*num < n)
            {
                num++;
            }
            
            vector<int> dp(n+1,INT_MAX);
            dp[0] = 0;
            for(int i=1;i<num+1;i++)
            {
                for(int j=1;j<n+1;j++)
                    if(j>=i*i)
                        dp[j] = min(dp[j],dp[j-i*i]+1);
            }
            return dp[n];
        }
    };
    

Log in to reply
 

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