- 原题链接🔗:完全平方数
- 难度:中等⭐️⭐️
题目
给你一个整数 n ,返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。
示例 1:
输入:n = 12
输出:3
解释:12 = 4 + 4 + 4
示例 2:
输入:n = 13
输出:2
解释:13 = 4 + 9
提示:
1 <= n <= 104
动态规划
动态规划(Dynamic Programming,简称DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学等领域中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常用于优化问题,特别是那些具有重叠子问题和最优子结构性质的问题。
动态规划的关键概念:
- 重叠子问题:原问题可以分解为多个子问题,而这些子问题会重复出现多次。
- 最优子结构:一个问题的最优解包含其子问题的最优解。
- 无后效性:一旦某个状态被确定,它就不受之后决策的影响。
- 状态转移方程:描述了问题的状态如何从先前的状态转移而来。
动态规划的步骤:
- 定义状态:确定问题的状态,通常用数组或变量来表示。
- 确定状态转移方程:找出状态之间的关系,即如何从一个状态推导出另一个状态。
- 确定初始状态和边界条件:设置问题的起始状态和基本情况。
- 计算顺序:确定如何计算所有状态,通常从初始状态开始,逐步计算到最终状态。
- 构造最优解:从最终状态开始,逆向回溯到初始状态,构造问题的最优解。
动态规划的应用实例:
- 背包问题:给定一组物品和一个背包,确定在不超过背包容量的前提下,背包中物品的最优组合。
- 最长公共子序列:找出两个序列的最长公共子序列。
- 最短路径问题:在加权图中找到从起点到终点的最短路径。
- 矩阵链乘问题:计算矩阵序列的最优乘法顺序,以最小化总的标量乘法次数。
题解
- 解题思路:
理解问题 给定一个正整数 n,目标是找到和为 n 的完全平方数的最少数量。完全平方数是指可以表示为某个整数的平方的数,例如 1, 4, 9, 16 等。
动态规划方法 这个问题可以通过动态规划(DP)来解决。我们定义一个数组 dp,其中 dp[i] 表示数字 i 可以由完全平方数相加得到的最少数量。
初始化 DP 数组 dp[0] 初始化为 0,因为和为 0 的最少数量是 0(不需要任何数)。 对于所有其他的 i,初始化 dp[i] 为一个非常大的数(例如 INT_MAX),表示暂时无法由完全平方数相加得到。
填充 DP 数组 对于每个 i 从 1 到 n,我们遍历所有可能的完全平方数 j * j(其中 j * j <= i),并更新 dp[i] 为 min(dp[i], dp[i - j*j] + 1)。这表示我们尝试用尽可能少的完全平方数来达到数字 i。
处理边界情况 确保处理所有可能的完全平方数,包括 1(因为 1 是最小的完全平方数,且经常出现在最优解中)。 考虑所有小于或等于 i 的完全平方数。
返回结果 最终,dp[n] 将包含和为 n 的完全平方数的最少数量
- c++ demo:
#include <iostream>
#include <vector>
#include <climits>
#include <cmath>// 动态规划求解和为n的完全平方数的最少数量
int numSquares(int n) {std::vector<int> dp(n + 1, INT_MAX);dp[0] = 0;for (int i = 1; i <= n; ++i) {int sqrt_val = static_cast<int>(std::sqrt(i));for (int j = 1; j <= sqrt_val; ++j) {dp[i] = std::min(dp[i], dp[i - j * j] + 1);}}return dp[n];
}// 主函数,用于测试
int main() {int n = 12; // 可以修改这个值来测试不同的输入std::cout << "The least number of perfect square numbers which sum to " << n << " is: " << numSquares(n) << std::endl;return 0;
}
- 输出结果:
The least number of perfect square numbers which sum to 12 is: 3
- 代码仓库:numSquares