Given a number N. Find the minimum number of squares of any number that sums to N. For Example: If N = 100 , N can be expressed as (10*10) and also as (5*5 + 5*5 + 5*5 + 5*5) but the output will be 1 as minimum number of square is 1 , i.e (10*10).
 
Example 1:
Input: N = 100
Output: 1
Explanation: 10 * 10 = 100
Example 2:
Input: N = 6
Output: 3
Explanation = 1 * 1 + 1 * 1 + 2 * 2 = 6
 
Your Task:
You don't need to read or print anyhting. Your task is to complete the function MinSquares() which takes N as input parameter and returns minimum number of squares needed to make N.
 
Expcted Time Complexity: O(N * sqrt(N) )
Expected Space Complexity: O(N)
 
Constraints:
1 <= N <= 10000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

	def MinSquares(self, n):

		# Code here

Solutions:
from math import sqrt, ceil

class Solution:

	def solve(self, n):
		if n < 0:
			return -1
		if n <= 3:
			return n
		mini = n
		temp = int(sqrt(n) + 1)
		for i in range(1, temp):
			ans = self.solve(n - i * i)
			if ans != -1:
				mini = min(mini, ans + 1)
		return mini

	def solve_memo(self, n, F):
		if n < 0:
			return -1
		if n <= 3:
			return n
		if F[n] != -1:
			return F[n]
		mini = n
		temp = int(sqrt(n) + 1)
		for i in range(1, temp):
			if i * i > n:
				break
			ans = 1 + self.solve_memo(n - i * i, F)
			mini = min(mini, ans)
		F[n] = mini
		return F[n]

	def MinSquares(self, n):
		F = [-1] * (n + 1)
		return self.solve_memo(n, F)


class Solution:

	def MinSquares(self, n):
		dp = [float('inf')] * (n + 1)
		dp[0] = 0
		dp[1] = 1
		for i in range(2, n + 1):
			for j in range(1, i + 1):
				if j * j > i:
					break
				dp[i] = min(dp[i], 1 + dp[i - j * j])
		return dp[n]


from math import sqrt

class Solution:

	def MinSquares(self, n):
		dp = [-1] * (n + 1)
		dp[0] = 0
		for i in range(1, n + 1):
			ans = float('inf')
			root = int(sqrt(i))
			for j in range(1, root + 1):
				temp = j ** 2
				ans = min(ans, 1 + dp[i - temp])
			dp[i] = ans
		return dp[n]


from math import sqrt

class Solution:

	def MinSquares(self, n):
		dp = [-1] * (n + 1)
		return self.solvemem(n, dp)

	def solvemem(self, n, dp):
		if n <= 0:
			return 0
		if dp[n] != -1:
			return dp[n]
		ans = n
		root = int(sqrt(n))
		for i in range(1, root + 1):
			temp = i ** 2
			ans = min(ans, 1 + self.solvemem(n - temp, dp))
		dp[n] = ans
		return dp[n]


import math

class Solution:

	def __init__(self):
		self.memo = {}

	def MinSquares(self, n):
		if n <= 3:
			return n
		if n in self.memo:
			return self.memo[n]
		res = n
		for i in range(1, n + 1):
			temp = i * i
			if temp > n:
				break
			else:
				res = min(res, 1 + self.MinSquares(n - temp))
		self.memo[n] = res
		return res


import math

class Solution:

	def MinSquares(self, n):
		dp = [float('inf')] * (n + 1)
		dp[0] = 0
		for i in range(1, n + 1):
			j = 1
			while j * j <= i:
				dp[i] = min(dp[i], dp[i - j * j] + 1)
				j += 1
		return dp[n]


import math

class Solution:

	def solve(self, n, dp):
		if n == 0:
			return 0
		if dp[n] != -1:
			return dp[n]
		root = int(math.sqrt(n))
		ans = n
		for i in range(1, root + 1):
			a = self.solve(n - i * i, dp) + 1
			ans = min(a, ans)
		dp[n] = ans
		return dp[n]

	def MinSquares(self, n):
		dp = [-1 for i in range(n + 1)]
		ans = self.solve(n, dp)
		return ans


import math

class Solution:

	def MinSquares(self, n):
		dp = [-1] * 10001
		dp[1] = 1
		dp[2] = 2
		dp[3] = 3
		for k in range(4, n + 1):
			if math.sqrt(k) % 1 == 0:
				dp[k] = 1
				continue
			ans_i = math.inf
			for num in range(1, 1 + int(math.sqrt(k))):
				ans_i = min(ans_i, dp[k - num ** 2])
			dp[k] = 1 + ans_i
		return dp[n]


from sys import maxsize
from math import sqrt

class Solution:

	def solve(self, n):
		if n <= 0:
			return 0
		mini = n
		temp = int(sqrt(n)) + 1
		for i in range(1, temp):
			ans = self.solve(n - i * i) + 1
			mini = min(ans, mini)
		return mini

	def solve_memo(self, n, F):
		if n < 0:
			return -1
		if n == 0:
			return 0
		if F[n] != -1:
			return F[n]
		mini = n
		temp = int(sqrt(n)) + 1
		for i in range(1, temp):
			ans = self.solve_memo(n - i * i, F)
			if ans != -1:
				mini = min(mini, ans + 1)
		F[n] = mini
		return F[n]

	def solve_tab(self, n):
		F = [-1] * (n + 1)
		F[0] = 0
		F[1] = 1
		for t in range(2, n + 1):
			temp = int(sqrt(t)) + 1
			mini = t
			for i in range(1, temp):
				ans = F[t - i * i] + 1
				mini = min(ans, mini)
			F[t] = mini
		return F[n]

	def MinSquares(self, n):
		F = [-1] * (n + 1)
		return self.solve_memo(n, F)


import math
import sys
max_int = sys.maxsize
min_int = -sys.maxsize - 1

class Solution:

	def MinSquares(self, n):
		dp = [max_int] * (n + 1)
		dp[0] = 0
		for i in range(1, n + 1):
			for j in range(1, math.floor(math.sqrt(i) + 1)):
				dp[i] = min(dp[i], 1 + dp[i - j * j])
		return dp[n]


from sys import maxsize
from math import sqrt

class Solution:

	def solve(self, n):
		if n <= 0:
			return 0
		ans = n
		for i in range(1, int(sqrt(n)) + 1):
			temp = i * i
			if temp <= n:
				ans = min(ans, 1 + self.solve(n - temp))
			else:
				break
		return ans

	def solve_memo(self, n, F):
		if n <= 0:
			F[0] = 0
			return F[0]
		if F[n] != -1:
			return F[n]
		ans = n
		for i in range(1, int(sqrt(n)) + 1):
			temp = i * i
			if temp <= n:
				ans = min(ans, 1 + self.solve_memo(n - temp, F))
			else:
				break
		F[n] = ans
		return F[n]

	def solve_tab(self, n):
		F = [maxsize] * (n + 1)
		F[0] = 0
		for i in range(1, n + 1):
			for j in range(1, int(sqrt(n)) + 1):
				temp = j * j
				if i - temp >= 0:
					F[i] = min(F[i], 1 + F[i - temp])
		return F[n]

	def MinSquares(self, n):
		return self.solve_tab(n)


class Solution:

	def MinSquares(self, n):
		dp = {}

		def solve(num):
			if num in dp:
				return dp[num]
			if num == 0:
				return 0
			if num < 0:
				return 99999999999
			i = 1
			mini = 99999999999
			while i * i <= num:
				mini = min(mini, 1 + solve(num - i * i))
				i += 1
			dp[num] = mini
			return mini
		return solve(n)