完全平方和的最小次数
#include<bits/stdc++.h>
using namespace std;
const int MAXN=20;
const int INF=0x3f3f3f3f;
//打印出每一个数的由完全平方数之和组成的最小次数
/*例如当n为10
数字:0 1 2 3 4 5 6 7 8 9 10
结果:0 1 2 3 1 2 3 4 2 1 2
*/
class Solution{public:vector<int> totalSquare(int n){vector<int> dp(n+1,INF);//无穷大方便后面的min的比较 dp[0]=0;//初始化 for(int i=0;i<=n;i++){for(int j=1;j*j<=i;j++){dp[i]=min(dp[i-j*j]+1,dp[i]);}}return dp;}
};
int main(){int n;vector<int> v;cin>>n;Solution solution;v=solution.totalSquare(n);for(auto go:v){cout<<go<<" ";}return 0;
}
欢迎批评指正!