计算机科学基础leetcode刷题动态规划 动态规划 2024-04-17 Source Edit History 279. 完全平方数 Problem: 279. 完全平方数 Code[]123456789101112131415161718class Solution {public: int numSquares(int n) { // dp[j]表示第j等于完全完全平方数的最少数量 vector<int> dp(n+1,INT_MAX); // dp[0] = 0 dp[0] = 0; // 组合问题 顺序无所谓 // 完全背包 顺序 for(int j=0;j<=n;j++){ // 物品是完全平方数 for(int i=1;i*i<=j;i++){ dp[j] = min(dp[j-i*i]+1,dp[j]); } } return dp[n]; }};