diff options
Diffstat (limited to 'perfect_squares.cpp')
-rw-r--r-- | perfect_squares.cpp | 23 |
1 files changed, 23 insertions, 0 deletions
diff --git a/perfect_squares.cpp b/perfect_squares.cpp new file mode 100644 index 0000000..677c4a0 --- /dev/null +++ b/perfect_squares.cpp @@ -0,0 +1,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); +} |