本文共 524 字，大约阅读时间需要 1 分钟。

题目

思路

所以该题的动态规划方程为：

设组成正整数n的最少完全平方数的个数为dp[n],则dp[n]=min(dp[n-11],dp[n-22],dp[n-33],……dp[n-jj])+1,其中要保证n-j*j>=0，

代码如下：

class Solution {public:    int numSquares(int n) {       if(n<4) return n;       vector
   
     dp(n+1);       for(int i=1;i<=n;i++){       	for(int j=1;i-j*j>=0;j++){       		dp[i]=min(dp[i],dp[i-j*j]+1);       		}       	}       	return dp[n];    }};
   

转载地址：http://zljmb.baihongyu.com/