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);
}
|