-
Notifications
You must be signed in to change notification settings - Fork 75
/
279_Perfect_Squares
62 lines (55 loc) · 1.4 KB
/
279_Perfect_Squares
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
Leetcode 279: Perfect Squares
--------------------------------------
Detailed Explanation can be found here: https://youtu.be/dOOzOsfj31I
C++:
----
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n+1, 0);
for(int x = 1; x <= n; ++x){
int min_val = x;
int y = 1, sq = 1;
while(sq <= x){
min_val = min(min_val, 1 + dp[x-sq]);
y++;
sq = y*y;
}
dp[x] = min_val;
}
return dp[n];
}
};
Java:
-----
class Solution {
public int numSquares(int n) {
int[] dp = new int[n+1];
for(int x = 1; x <= n; ++x){
int min_val = x;
int y = 1, sq = 1;
while(sq <= x){
min_val = Math.min(min_val, 1 + dp[x-sq]);
y++;
sq = y*y;
}
dp[x] = min_val;
}
return dp[n];
}
}
Python3:
--------
class Solution:
def numSquares(self, n: int) -> int:
dp = [0]*(n+1)
for x in range(1, n+1):
min_val = x;
y, sq = 1, 1
while sq <= x:
min_val = min(min_val, 1 + dp[x-sq])
y += 1
sq = y*y
dp[x] = min_val
return dp[n]
****** Please Subscribe Knowledge Center: http://youtube.com/c/KnowledgeCenter ********