LeetCode-Perfect Squares

这道题可以使用DP的方法来解,主要思路是找出状态转移。其状态为n之前每一个数字所对应的结果。转移方程为dp[i]=1(i是平方数)或dp[i]=min{dp[i-1],dp[i-4],dp[i-9]…}+1(i不是平方数,就是如果可以找到平方数之前的一个数字,然后加上一个平方数,就可以得到i所对应的的最佳值)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
private:
vector<int> nums;
int *dp;
int pos;
public:
int numSquares(int n) {
dp=new int[n+1];
genNums(n);
if(n==nums[nums.size()-1]) return 1;
pos=0;
dp[1]=1;
for(int i=2;i<=n;i++){
if(isSquare(i)) dp[i]=1;
else dp[i]=getMin(i)+1;

}
return dp[n];
}

void genNums(int n){
for(int i=1;;i++){
int ii=i*i;
if(ii<=n) nums.push_back(ii);
else break;
}
}

int getMin(int n){
int minNum=dp[n-1];
for(int i=1;i<nums.size();i++){
if(n-nums[i]>0){
minNum=min(minNum,dp[n-nums[i]]);
}
}
return minNum;
}
bool isSquare(int n){
if(n==nums[pos]) return true;
if(n>=nums[pos] && pos<nums.size()-1) pos++;
return false;
}
};