给定一个数input，求最少数N（加和数为1,2..n的平方数）,使N个数的和等于input

#coding=utf-8

#求最少硬币数

import sys 

#str = input()

#print(str)

input=12

nums = []

n=1

while n*n<input:

    nums.append(n*n)

    n=n+1

state=[]

for i in range(input):

    state.append(i)

min1=input

for i in range(input):

    for j in nums:

        if j<=i:

            state[i]=min(state[i],1+state[i-j])

print(state[input-1])