这道题看着简单，但是自己没啥思路。
有三种方法
法一：动态规划，状态转移方程式 dp[i] = min(dp[i], dp[i - j*j]+1) ,其中i是当前所求的数，dp[i]表示最少能用几个完全平方数表示i这个数，j*j 表示可能的完全平方数
法二：BFS自上而下，一个个减去可能的完全平方数，直到得到0，即可求解。
法三：BFS自下而上，从0开始，一个个加完全平方数，直到得到n，求解。
两种BFS方法都用一个数组，存储已经计算过的数据，用于剪枝。
题目
法一
法二-三
网友评论