Google 电面

1. def minSqrSum(num):
   
2.     opt = [[] for i in range(0, num+1)]
   
3.     sq = 1
   
4.     while sq**2<num:
   
5.         sq += 1
   
6.     sqrs = [i**2 for i in range(1,sq)]
   
7.     for i in sqrs:
   
8.         opt[i] = [i]
   
9.     for i in range(1, num+1):
   
10.         for sq in sqrs:
    
11.             if i+sq>num:
    
12.                 break
    
13.             tmp = opt[i] + [sq]
    
14.             if not opt[i+sq] or len(tmp)<len(opt[i+sq]):
    
15.                 opt[i+sq] = tmp
    
16.     return opt[num]

复制代码

1. def minSqrSum(num):     opt = [[] for i in range(0, num+1)]     sq = 1     while sq**2<num:         sq += 1     sqrs = [i**2 for i in range(1,sq)]     for i in sqrs:         opt[i] = [i]     for i in range(1, num+1):         for sq in sqrs:             if i+sq>num:                 break             tmp = opt[i] + [sq]             if not opt[i+sq] or len(tmp)<len(opt[i+sq]):                 opt[i+sq] = tmp     return opt[num]

复制代码

1. def minSqrSum(num):
   
2.     opt = [[] for i in range(0, num+1)]
   
3.     sq = 1
   
4.     while sq**2<num:
   
5.         sq += 1
   
6.     sqrs = [i**2 for i in range(1,sq)]
   
7.     for i in sqrs:
   
8.         opt[i] = [i]
   
9.     for i in range(1, num+1):
   
10.         for sq in sqrs:
    
11.             if i+sq>num:
    
12.                 break
    
13.             tmp = opt[i] + [sq]
    
14.             if not opt[i+sq] or len(tmp)<len(opt[i+sq]):
    
15.                 opt[i+sq] = tmp
    
16.     return opt[num]

复制代码

感觉可以转换成dp找钱的题

dp[n]=min(dp[n-1^2], dp[n-2^2]...dp[n-k^2])+1     k<=sqrt(n)

可以从1到n计算最少组合数，复杂度是n的3/2次方；
利用四平方和定理，可以提升到O(n);
不过貌似都是伪多项式时间的

用四平方和定理明显overkill，只要能正确写出dp解法即可

https://leetcode.com/problems/perfect-squares/