[HOT 100]今日一练------完全平方数

题目链接https://leetcode.cn/problems/perfect-squares/?envTypestudy-plan-v2envIdtop-100-liked思路动态规划dp[i]表示i这个数需要多少个完全平方数来凑最坏的情况应该为这个数全部用1来凑因此我们初始化为这样接下来我们将讨论dp[i]可能存在的情况为两种就使用初始化的最差情况使用掉一个完全平方数后找剩下的数的dp值 1[这里1是因为我们用掉了一个完全平方数要算上这个数]即dp[i - 完全平方数] 1那么据上述我们可以发现为了实现以上思路我们必须要有每个dp[i]的值且我们要列举不同的完全平方数因此我们需要用两层循环来进行实现代码class Solution { //动态规划 public int numSquares(int n) { //dp[i]表示i这个数要多少个完全平方数来凑 int[] dp new int[n1]; //初始化: 最坏情况全用1来凑 for(int i 1; i n; i) dp[i] i; //动态规划 for(int i 1; i n; i) for(int j 1; j * j i; j) dp[i] Math.min(dp[i], dp[i - j*j]1); return dp[n]; } }