完全平方数

public int numSquares(int n) {
    int[] dp = new int[n + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0; // 凑 0 不需要任何平方数
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j * j <= i; j++) { // 枚举最后一个平方数
            dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
        }
    }
    return dp[n];
}

def numSquares(n: int) -> int:
    dp = [float("inf")] * (n + 1)
    dp[0] = 0  # 凑 0 不需要任何平方数
    for i in range(1, n + 1):
        j = 1
        while j * j <= i:  # 枚举最后一个平方数
            dp[i] = min(dp[i], dp[i - j * j] + 1)
            j += 1
    return dp[n]

func numSquares(n int) int {
    dp := make([]int, n+1)
    for i := 1; i <= n; i++ {
        dp[i] = math.MaxInt32
    }
    // dp[0] = 0：凑 0 不需要任何平方数
    for i := 1; i <= n; i++ {
        for j := 1; j*j <= i; j++ { // 枚举最后一个平方数
            dp[i] = min(dp[i], dp[i-j*j]+1)
        }
    }
    return dp[n]
}

pub fn num_squares(n: i32) -> i32 {
    let n = n as usize;
    let mut dp = vec![i32::MAX; n + 1];
    dp[0] = 0; // 凑 0 不需要任何平方数
    for i in 1..=n {
        let mut j = 1;
        while j * j <= i { // 枚举最后一个平方数
            dp[i] = dp[i].min(dp[i - j * j] + 1);
            j += 1;
        }
    }
    dp[n]
}