aboutsummaryrefslogtreecommitdiff
path: root/perfect_squares.cpp
blob: 677c4a0fc73ce723645f31e44451e77846f64747 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include "leetcode.h"

class Solution {
public:
  int numSquares(int n) {
    vector<int> dp(n + 1, INT_MAX);
    dp[0] = 0;
    for (int target = 1; target <= n; target++) {
      int mmCount = INT_MAX;
      for (int num = 1; num <= sqrt(target); num++) {
        int sqNum = pow(num, 2), curr = 1 + dp[target - sqNum];
        mmCount = min(mmCount, curr);
      }
      dp[target] = mmCount;
    }
    return dp[n];
  }
};

int main() {
  Solution obj;
  cout << obj.numSquares(12);
}