校招真题练习035 最少立方数之和(小米)

题目描述
给出一个数字N（0<N<1000000）,将N写成立方数和的形式，求出需要的最少立方数个数。
例如N=17，1+8+8 = 17，最少需要3个立方数，则输出3。
N= 28,1+1+1+1+8+8+8=28, 需要7个立方数，1+27=28,需要2个立方数，所以最少立方数为2，则输出2。

输入描述:
一个数字N（0<N<1000000）

输出描述:
最少立方数个数

 1 def main():
 2     n = int(input())
 3     power = set()
 4     base = 1
 5     while base**3 <= n:
 6         curnum = base**3
 7         if curnum == n:
 8             print(1)
 9             return
10         power.add(curnum)
11         base += 1
12     level = 1
13     target = {n}
14     while target:
15         cur = set()
16         for i in target:
17             for e in power:
18                 if i-e in power:
19                     print(level+1)
20                     return
21                 if i-e > 0:
22                     cur.add(i-e)
23         target = cur
24         level += 1
25 
26 if __name__ == '__main__':
27     main()

算法思路：BFS