应用题-动态规划-完全平方数( 完全背包 )
- 版权声明：本站原创文章，于2026-05-19，由 管理员 发表。
- 转载请注明： 应用题-动态规划-完全平方数( 完全背包 ) | CodeGarden
```python
class Solution:
# 一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
# 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
def numSquares(self, n: int) -> int:
# 完全背包
# 任取n中的数 装入容积为n的背包。
# dp[ i ]表示容积为i的背包 达到最大价值i 所需的最小物品数
MAX_ = float( 'inf' )
dp = [ MAX_ for _ in range( n + 1 ) ]
dp[ 0 ] = 0
for i in range( 1, n + 1 ):
v = i * i
for j in range( v, n + 1 ):
dp[ j ] = min( dp[ j ], dp[ j - i * i ] + 1 )
return dp[ n ]
```