dp c++


  • 0
    A
    class Solution {
    public:
      int numSquares(int n) {
        const unsigned m = floor(sqrt(n));
        vector<int> nums(m);
    
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i <= n; ++i) {
          for (int j = 1; j <= m; ++j) {
            if (i >= j * j) {
              dp[i] = min(dp[i], dp[i - j * j] + 1);
            }
          }
        }
    
        return dp[n];
      }
    };
    
    

Log in to reply
 

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