LeetCode 279. Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

分析:建立一个n+1长度的数组dp,dp[i]表示i这个数构成平方和需要数字的最小个数。
当j*j<i的时候,temp中保存j从1开始每加1得到的dp[i-j*j] + 1的最小值~
当j*j=i的时候,dp[i]的值就直接为1~
从2一直到n可以计算出dp[i]的所有值~
最后return dp[n]的值~

 

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版