力扣热门100题之完全平方数

思路定义dp[i]凑成数字 i 所需的最少完全平方数个数转移dp[i] min(dp[i - j*j] 1)初始dp[0] 0其余先设为很大的值通俗解释要凑i可以从i - j²加一个平方数j²过来所以dp[i]就是所有可能里最小的那个比如dp[4] dp[0]1 1dp[5] dp[4]1 2dp[12] dp[8]1 dp[4]2 3最简单记忆和为 i 的最少平方数 前面某个位置 1 个平方数取最小完整代码实现class Solution { public int numSquares(int n) { int[] dp new int[n 1]; // 初始化一个很大的数 for(int i 1;in;i){ dp[i] Integer.MAX_VALUE; } dp[0] 0; for(int i 1;in;i){ // 尝试所有平方数 j*j for(int j 1;j * ji;j){ dp[i] Math.min(dp[i],dp[i - j*j] 1); } } return dp[n]; } }