动态规划——完全平方数（python）

思路dp[i]定义为凑成i所需要的最少完全平方数为dp[i]。求的是最少数量。状态转移方程dp[i]min(dp[i-j**2]1,dp[i])def perfectSquares(n): #q求凑成i的最少完全平方数的数量 dp[float(inf)]*(n1) dp[0]0 for i in range(1,n1): j1 while j*ji: dp[i]min(dp[i-j**2]1,dp[i]) j1 return dp[n] def main(): nint(input()) resperfectSquares(n) print(res) if __name____main__: main()