力扣——完全平方数

题目链接：

链接

题目描述：

思路：

用动态规划，设$i$的最少数量是$dp(i)$，最多数量是$i$，如1+1+…+1
则 d p ( i ) = m i n { i , d p ( i − j ∗ j ) + 1 } dp(i)=min\\{ i,dp(i-j*j)+1 \\} dp(i)=min{i,dp(i−j∗j)+1}
这里为什么是$dp(i-j\ast j)+1$，因为要得到$i$减去一个平方数后的最小组成数量，那么$i$的最小组成数量就是减去平方数后的最小组成数量+1，这个1就代表减去的这个平方数

实现代码：

class Solution { public int numSquares(int n) { int[] dp = new int[n+1]; dp[0] = 0; for(int i = 1; i <= n; i++){ int minn = i; for(int j = 1; i - j * j >=0; j++){ minn = Math.min(minn, dp[i - j * j] + 1); } dp[i] = minn; } return dp[n]; }}