#1699平方和(Sum of square number)c++

問題を見るだけでは何も考えられない.
表に記入して、ルールを探してみました.

ここから得たいくつかの手がかり
dp[1]=1
dp[i*i]=1(一部の数の平方数は1)
dp[3]=dp[3-1*1]+1
dp[5]=dp[5-2*2]+1
dp[6]=dp[6-2*2]+1
…
このようなルールを見つけることができます
(うち+1は1*1という意味ではなく、1つ)
しかし、常にdp[N]からN未満の最大二乗数を減算する値は答えではありません.
e.g.
dp[43]=dp[43-6*6]+1=dp[7-2*2]+2=dp[3-1*1]+3=5
dp[43]=dp[43-5*5]+1=dp[18-3*3]+2=dp[9-3*3]+3=3
この文は複文を用いてdp[n]のn以下の平方数を1つずつ減算し、1を加算して最小値を比較して保存すべきである.
参照として、dp[0]=0に初期化する
(e.g.dp[9]=dp[9-3*3]+1=dp[0]+1、この場合)

Boottom up方式

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
const int MAX = 100000;

int sqaureSum(int n) {
	vector<int>dp(n + 1, 0);

	for (int i = 1; i <= n; i++) {
		dp[i] = i;
		for (int j = 1; j * j <= i; j++) {
			dp[i] = min(dp[i], dp[i - j * j] + 1 );
		}
	}
	return dp[n];
}

int main() {
	int n;
	cin >> n;

	if (n > MAX)
		exit(EXIT_FAILURE);

	cout<<sqaureSum(n)<<endl;

	return 0;
}

上下移動

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
const int MAX = 100000;

int dp[MAX + 1];

int sqaureSum_(int n) {
	if (dp[n] != -1) return dp[n];
	dp[n] = n;
	for (int i = 1; i * i <= n; i++) {
		dp[n] = min(dp[n], sqaureSum_(n - (i * i)) + 1);
	}
	return dp[n];
}

int main() {
	int n;
	cin >> n;

	if (n > MAX)
		exit(EXIT_FAILURE);
	
	dp[0] = 0;
	for (int i = 1; i <= MAX; i++)
		dp[i] = -1;

	cout <<sqaureSum_(n) << endl;

	return 0;
}

top-downとbottom-up方式のメモリと時間の差はほぼ2倍です.