What's wrong with this cpp dp solution ?


  • 0
    J

    The code is:

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

    each time I submitted, it get different error message, sometime it says "run time error", more often "wrong answer", but it runs fine else where.

    for example, now I'm getting this:
    Input:
    3
    Output:
    2
    Expected:
    3

    But when I run it on my laptop, the answer is the correct one, "3".

    Would really appreciate if anyone can tell me the problem.


  • -1
    S

    You'd better AC the problem Coin Change first.

    https://leetcode.com/problems/coin-change/


Log in to reply
 

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