Perfect Squares
問題概要
https://gyazo.com/aa3d345a9592eb620b1b6fb361602666
上図のような任意の数字nが与えられる
任意の数字が複数あるとして、それらの二乗の和がちょうどnとなるような数字の集合の最小数を答えよ、という問題
解法
が$ 10^3くらいのオーダーでTLE判定となった Approach 1の総当りとほぼ同じことをやってしまっていた
解説を読んでDPで以下の式を使えば解けることが判明した それを元に解いたコードを下に貼っている
$ Square(n) = Square(n-k)+1(ただし$ kは何らかの数字の二乗)
関連
DPでAC
code:dp.cpp
class Solution {
public:
int numSquares(int n) {
vector<int> sq = {};
vector<int> dp = {0};
for (int i=1; pow(i, 2)<=n; i++) sq.push_back(pow(i, 2));
for (int i=1; i<=n; i++) {
int val = INT_MAX;
for (int j=0; j<sq.size() && i-sqj>=0; j++) val = min(val, dp[i-sqj]); dp.push_back(val+1);
}
}
};
こちらの時間計算量は$ O(N \times \sqrt{N})
内部のループは最大で$ \sqrt{N}回回るため.