LeetCode-Perfect Squares

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

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;
    }
};