正の整数nを与え,nより小さい完全な平方数の加算とnに等しい最小数を見つけた.
本題はleetcodeに由来する
----------------------------------------------------------------
考え方:
動的計画整数iに必要な最小二乗和数を1つのvectorで保存します.
1 vectorを初期化します.v[0]=0;次に、配列の数がnより小さい場合にループします.各必要最小平方数の和を巡回する
コード:
コード2:
----------------------------------------------------------------
考え方:
動的計画整数iに必要な最小二乗和数を1つのvectorで保存します.
1 vectorを初期化します.v[0]=0;次に、配列の数がnより小さい場合にループします.各必要最小平方数の和を巡回する
コード:
int numSquares(int n) {
if(n<=0)
return 0;
vector vec;
vec.push_back(0);
while(vec.size()<=n){
int m=vec.size();
int minNum=INT_MAX;
for(int i=1;i*i<=m;i++){ // m
minNum=min(minNum,vec[m-i*i]+1);
}
vec.push_back(minNum);
}
return vec[n];
}
コード2:
int numSquares(int n) {
if(n<=0)
return 0;
vector vec(n+1,INT_MAX);
vec[0]=0;
for(int i=1;i<=n;i++){
for(int j=1;j*j<=i;j++){
vec[i]=min(vec[i],vec[i-j*j]+1);
}
}
return vec[n];
}