[leetcode]279 Perfect Squares(DP,四平方和定理)

1.四平方和の定理
定理は,各正の整数が4つの整数の二乗和として表すことができることを示している.つまり、この問題の答え<=4、私たちはまず配列の中で平方和を前に処理することができて、それから2階のfor循環暴力循環は1、2を判断して、ついでに残りの検査で3かどうかを検査することができて、すべてそうでなければ、4.
2. 
やはり4の平方と定理を利用して、しかし多くの技巧を使って、この解法はネット上の解答を参考にします:4の平方と定理に基づいて、任意の1つの正の整数はいずれも4つの整数の平方和を表すことができて、実は4つの以内の平方数の和を表すことができて、それでは結果を返して1,2,3あるいは4の中の1つだけあると言って、まず私达はデジタル化を简単にして、1つの数に因子4が含まれている場合、私たちは4をすべて取り除くことができ、結果に影響を与えません.例えば、2と8、3と12など、戻った結果は同じで、読者は自分でもっと多くの栗を挙げることができます.もう一つ簡略化できるところは、1つの数を8余り7で割ると、4つの完全な平方数からなるに違いない.ここでは証明しない.私も証明しないから、読者は自分で例を挙げて検証することができる.では、2つのステップを完了すると、大きな数が小さくなる可能性があります.演算時間が大幅に減少します.次に、2つの平方数の和に分解してみましょう.分解に成功すると、1または2に戻ります.そのうちの1つの平方数は0になる可能性があります.(注:入力したnは正の整数であるため、2つの平方数がいずれも0の場合はありません).下に注意!!a + !!bこの表現は、多くの人がこの意味をあまり理解していないかもしれませんが、実は簡単で、感嘆符!表示论理取反,那么1个正整数论理取反为0,再取反为1,所以用2个感嘆符!!の役割は、aとbが正の整数であるかどうかを見て、すべて正の整数であれば2を返し、1つだけ正の整数であれば1を返します.コードは以下の通りです.

class Solution {
public:
    int numSquares(int n) {
        while (n % 4 == 0) n /= 4;
        if (n % 8 == 7) return 4;
        for (int a = 0; a * a <= n; ++a) {
            int b = sqrt(n - a * a);
            if (a * a + b * b == n) {
                return !!a + !!b;
            }
        }
        return 3;
    }
};

3
すぐに状態遷移方程式が考えられるわけではなく,dp[i]はiを構成する最小二乗数の個数を表し,この値が最大でそれ自体である(いずれも1からなると見なす).状態遷移については,この数を構成する最小値がそれ自体であるか,あるいは前のある数+1平方数であるか(したがって,値に1を加えると見なす).0-1リュックサックのような考え方にもなりますので、ご自身でお楽しみください.

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