题目地址

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

题目大意

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

解题思路

动态规划思想，dp[i]表示i的问题解, 对i开方,得到最大的平方根maxRoot, 则i的某个平方和可表示为：
i = \(j_1^2\) +\(j_2^2\) + ...+ \(j_k^2\)
= \(j_m^2\) + (\(j_1^2\) + ... + \(j_{m-1}^2\) + \(j_{m+1}^2\) + ... + \(j_k^2\))
= x + dp[i-x]
其中，k <= i, 0 < \(j_k\), x <= maxRoot, 故而
dp[i] = 1 + min(dp[i- \(1^2\)], dp[i-\(2^2\)],...,dp[i-\({maxRoot}^2\)]), 为方便计算，令dp[0] = 0

c++代码

class Solution {
public:
    int numSquares(int n) {
       vector<int> dp(n+1, 0);
       int cnt = 0;
        for (int i = 1; i <= n; i++) {
           int maxRoot = sqrt(i);
           int minCnt = i;
           while (maxRoot) {
               minCnt = min(minCnt, dp[i - maxRoot * maxRoot]);
               maxRoot--;
           }
           dp[i] = 1 + minCnt; 
        }

        return dp[n];
    }
};

go代码

func numSquares(n int) int {
    var dp = make([]int, n + 1)
    for i := 1; i <= n ; i++{
        maxRoot := int(math.Sqrt(float64(i)))
        minCnt := i
        for ;maxRoot > 0;maxRoot-- {
            minCnt = int(math.Min(float64(minCnt), float64(dp[i - maxRoot * maxRoot])))
        }
        dp[i] = 1 + minCnt
    }

    return dp[n]
}

扩展

求出平方和展开式？

func numSquares2(n int) (int, []int) {
    var dp = make([]int, n + 1)
    var numCombGroup = [][]int{{}}
    for i := 1; i <= n ; i++{
        maxRoot := int(math.Sqrt(float64(i)))
        minCnt := i
        remainNum := 0
        for ;maxRoot > 0;maxRoot-- {
            if minCnt > dp[i - maxRoot * maxRoot] {
                minCnt = dp[i - maxRoot * maxRoot]
                remainNum = i - maxRoot * maxRoot
            }
            minCnt = int(math.Min(float64(minCnt), float64(dp[i - maxRoot * maxRoot])))
        }
        dp[i] = 1 + minCnt
        numComb := []int{i - remainNum}
        numComb = append(numComb, numCombGroup[remainNum]...)
        numCombGroup = append(numCombGroup,numComb)
    }

    return dp[n], numCombGroup[n]
}