Python算法例1 完美平方

例1 完美平方

1. 问题描述

给定一个正整数n，找到若干个完全平方数（例如：1，4，9，…），使得它们的和等于n，完全平方数的个数最少。

2.问题示例

给出n=8，返回2，因为8=4+4；给出n=25，返回1，因为25=25。

3.代码实现

可以使用动态规划的思想来解决这个问题，具体步骤如下：

1. 定义一个长度为n+1的数组dp，dp[i]表示数字i最少可以由几个完全平方数相加得到。

2. 初始化dp[0]=0，因为0本身就是完全平方数。

3. 对于每个数字i，从1开始枚举所有小于等于i的完全平方数jj，然后更新dp[i]的值，即dp[i]=min(dp[i], dp[i-jj]+1)。

4. 最终dp[n]就是答案。

import math
 
def numSquares(n: int) -> int:
    dp = [float('inf')] * (n+1)
    dp[0] = 0
    for i in range(1, n+1):
        for j in range(1, int(math.sqrt(i))+1):
            dp[i] = min(dp[i], dp[i-j*j]+1)
    return dp[n]
 
print(numSquares(8))
print(numSquares(25))

 运行结果：

可以使用广度优先搜索（BFS）的方法来解决这个问题。具体步骤如下：

1. 定义一个队列，将初始状态 (n, 0) 入队，其中 n 表示当前剩余的数字，0 表示当前已经使用的完全平方数的个数。

2. 进入循环，直到队列为空为止。在每一轮循环中，取出队首元素 (num, count)。

3. 判断 num 是否为完全平方数，如果是，则返回 count+1，即找到了最少的完全平方数个数。

4. 否则，对于从 1 开始的每个完全平方数 i^2，计算新的剩余数字 new_num = num - i^2，并将 (new_num, count+1) 入队。

import math
from collections import deque
 
def numSquares(n: int) -> int:
    queue = deque([(n, 0)])
    visited = set([n])
 
    while queue:
        num, count = queue.popleft()
 
        if num == 0:
            return count
 
        for i in range(1, int(math.sqrt(num)) + 1):
            new_num = num - i*i
            if new_num not in visited:
                queue.append((new_num, count + 1))
                visited.add(new_num)
 
    return -1  # 如果无法找到完全平方数相加等于 n 的情况
 
# 测试样例
print(numSquares(8))  # 输出 2
print(numSquares(25))  # 输出 1

运行结果：