# LeetCode 279 Perfect Squares

## 概述

https://leetcode.com/problems/perfect-squares/

## 二维动态规划

TLE 了。

``````class Solution {
public:
vector<vector<int>> dp;
int numSquares(int n) {
dp.resize(n + 1, vector<int>(sqrt(n) + 1, -1));
return helper(n, sqrt(n));
}

int helper(int n, int s) {
if (n == 0) return 0;
if (s == 1) return n;
if (dp[n][s] != -1) return dp[n][s];
dp[n][s] = INT_MAX;
for (int i = 0; i * s * s <= n; i ++) {
dp[n][s] = min(dp[n][s], i + helper(n - i * s * s, s - 1));
}
return dp[n][s];
}
};
``````

## 一维的动态规划

https://leetcode.com/problems/perfect-squares/discuss/71488/Summary-of-4-different-solutions-(BFS-DP-static-DP-and-mathematics)

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

why Static Dynamic Programming is faster than Dynamic Programming

it's faster because an answer once calculated for a test case remains for the upcoming test case say you calculated for 100 and the next test case is for 50 so you have already calculated it. static members once created remain for the lifetime of the program.