answer | Python Fiddle

# Write your code below!
import math
import heapq

from collections import namedtuple
from collections import deque

class SubProblem:
    def __init__(self, n, coin_count, coin_sum, coins):
        self.n = n
        self.coin_count = coin_count
        self.coin_sum = coin_sum
        self.coins = coins
    
    def __lt__(self, other):
        return (self.coin_count < other.coin_count or self.n < other.n)
        
    def __str__(self):
        return "n=" + str(self.n) 
        + " coin_count=" + str(self.coin_count)
        + " coins=" + str(self.coins)
        + " coin_count=" + str(self.coin_count)
    
class State:
    def __init__(self, **kwds):
        self.__dict__.update(kwds)

def answer(n):
    state = State(sub_problems=[], min_coin_count=100)
    first_sub_problem = SubProblem(n=n, coin_count=0, coin_sum=0, coins=[])
    state.sub_problems.append(first_sub_problem)
    while len(state.sub_problems) > 0:
        sub_problem = heapq.heappop(state.sub_problems)
        print "Solving subproblem: ", sub_problem
        if sub_problem.n == 0:
            min_coin_count_for_sub_problem = sub_problem.coin_count
            state.min_coin_count = min([min_coin_count_for_sub_problem, state.min_coin_count])
        elif sub_problem.n == 1:
            min_coin_count_for_sub_problem = sub_problem.coin_count + 1
            state.min_coin_count = min([min_coin_count_for_sub_problem, state.min_coin_count])
        else:
            add_new_sub_problems(sub_problem, state)
            #print "number of sub problems = ", len(state.sub_problems)
    return state.min_coin_count

def add_new_sub_problems(sub_problem, state):
    # If we have aleady a better solution with less coins than
    # coint_count_so_far, then we do not need to solve this   
    # sub_problem as it is not the final solution.
    if sub_problem.coin_count > state.min_coin_count:
        return
    
    n = sub_problem.n
    square_root = n**0.5
    max_coin_value =int( math.ceil(square_root))
    #print "max_coin_value=", max_coin_value
    for i in reversed(range(1,max_coin_value + 1)):
        remaining_value = n-(i*i)
        if remaining_value >= 0:
            #print "remaining_value = ", remaining_value
            new_sub_problem = sub_problem
            new_sub_problem = SubProblem(n=remaining_value, coin_count=sub_problem.coin_count+1, coin_sum=sub_problem.coin_sum+(i*i), coins=sub_problem.coins + [i])
            heapq.heappush(state.sub_problems, new_sub_problem)
            #print "Added new sub problem for n=", new_sub_problem.n

#for i in xrange(1,10):   
#    coin_count = answer(i)
#    print "min number of coins used for", i, " is ", coin_count

coin_count = answer(999)
print "min number of coins used for", 1000, " is ", coin_count

Python Fiddle

Python Cloud IDE