[leetcode,动态规划] 完全平方数

发布时间:2023年12月18日

给你一个整数?n?,返回?和为?n?的完全平方数的最少数量?。

完全平方数?是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,149?和?16?都是完全平方数,而?3?和?11?不是。

示例?1:

输入:n = 12
输出:3 
解释:12 = 4 + 4 + 4

示例 2:

输入:n = 13
输出:2
解释:13 = 4 + 9

?

提示:

  • 1 <= n <= 10^4

解题分析

在使用动态规划解决问题时,我们通常需要一个动态规划数组,这个数组可以是一维的,二维的,甚至是三维的。数组的维度取决于我们怎样才能清晰地描述这个问题。在本题中,一维数组就足够了。

然后,我们需要设置边界条件。由于每个整数n都可以拆分为n个1的平方相加,因此我们可以先用一个for循环,从1到n,将dp[i]初始化为i。

接下来,我们需要考虑递推公式。实际上,递推公式可以翻译为:$dp[i]=\min(dp[i-1]+1,dp[i-4]+1,\ldots,dp[i-k*k]+1)$,其中$i-k*k$必须满足大于等于0。

假设当n-1时,递推公式成立,那么我们可以推导出当n时,递推公式同样成立。因此,对所有的正整数n,这个递推公式都是成立的。

最后,我们直接返回$dp[n]$,这就是我们的答案。

?代码实现
#include <iostream>
using namespace std;

int dp[10005];

int main(){
	int n; scanf("%d",&n);
	for(int i=0;i<=n;i++){
		dp[i]=i;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;i-j*j>=0;j++){
			dp[i]=min(dp[i],dp[i-j*j]+1);
		}
	}
	printf("%d",dp[n]);
	return 0;
}

文章来源:https://blog.csdn.net/StudyingPanda/article/details/135061941
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。