无意间看到了这么一个题:
LeetCode279:完全平方数,动态规划解法超过46%,作弊解法却超过97%
=============================================
使用Python编写动态规划算法来解决该问题:
import numpy as np
n=int( input("num:") )
op_num = 0
dp = np.zeros(n+1, dtype=np.int64)
dp[0]=1
for i in range(1, n+1):
dp[i]=11111111
for j in range(1, i+1):
if j*j>i:
op_num += 1
break
if j*j==i:
dp[i]=1
op_num += 1
break
op_num += 1
dp[i]=min(dp[i-j*j]+1, dp[i])
print("="*30)
print(dp)
print("op_num:", op_num)
print("ans:", dp[n])
效果:
=============================================