资讯详情

题目链接：279. 完全平方数 - 力扣（LeetCode）

 

 

 

 

 

 

 

 

 

 

 

 

 

 

解析：

简单dp

class Solution {
public:int numSquares(int n) {vector<int> sq;for (int i = 1; i <= 100; i++) {sq.push_back(i * i);}int dp[10010];for (int i = 0; i < 10010; i++) dp[i] = 0x7fffffff;dp[0] = 0;for (int i = 1; i <= n; i++) {for (int j = 0; j < sq.size(); j++) {if (sq[j] > i) break;dp[i] = min(dp[i], dp[i - sq[j]] + 1);}}return dp[n];}
};