首页 > 其他分享 >力扣-279-完全平方数

力扣-279-完全平方数

时间:2022-11-03 19:47:58浏览次数:47  
标签:平方 背包 numSquares int 完全 力扣 279 dp

有没有可能是个数学题
保证一定能通过若干个完全平方数凑整,再不济可以11111111…
我想到了动态规划的斐波那契数列,但似乎并不是一个线性dp…
瞄评论,瞄到了“背包”,那这里应该是一个完全背包
很明显n就是背包容量…
背包是限定容量情况下能放的最大价值…
物品应该是小于n的所有完全平方数
但是这么放能保证数量最少吗?

背包的定义是前i件物品,体积不超过j所能达到的最大价值
体积等于j选中物品的最小数量

我写了个递归出来,似乎是对的,但是疯狂超时

int numSquares(int n) {
	if (n == 1) return 1;
	// 至多不会超过n个1组成
	int minSum = n;
	// 更像是一个树型dp
	int i = 2;
	while (pow(i, 2) <= n) {
		if (pow(i, 2) == n) return 1;
		else minSum = min(minSum,1+numSquares(n - pow(i, 2)));
		i++;
	}
	return minSum;
}

啊,我应该把这个递归改成动态规划

int numSquares(int n) {
	// dp[i]表示i最少由多少个完全平方数组成
	vector<int> dp(n+1,n);
	int j = 1;
	for (int i = 1; i <= n; i++) {
		j = 1;
		while (pow(j, 2) <= i) {
			if (pow(j, 2) == i) dp[i] = 1;
			else dp[i] = min(dp[i],1 + dp[i - pow(j, 2)]);
			j++;
		}
		// cout << dp[i] << " ";
	}
	return dp[n];
}

其实感觉还是差了点优雅,但是自己的思路一下子也没看出来怎么优雅

然后这题果然是个数学题,四平方和定理

标签:平方,背包,numSquares,int,完全,力扣,279,dp
From: https://www.cnblogs.com/yaocy/p/16855598.html

相关文章

  • 力扣-152-乘积最大的子数组
    对于dp[i],如果nums[i-1]>0,dp[i-1]也>0,那就是dp[i-1]*nums[i-1]如果<0,>0,那就是nums[i-1]0,<0,那就是nums[i-1]<0,<0,那就是dp[i-1]*nums[i-1]同样参考最大子数和,还需......
  • 力扣 二叉树 算法+题目 整理
    二叉树基础包括三种遍历,建树和遍历的方法。二叉树遍历力扣144,94,145二叉树前中后序遍历使用递归或者迭代空间复杂度都是o(n),而通过morris遍历则可以达到o(1),其介绍......
  • 力扣1668(java&python)-最大重复子字符串(简单)
    题目:给你一个字符串 sequence ,如果字符串word 连续重复 k 次形成的字符串是 sequence 的一个子字符串,那么单词 word的重复值为k。单词word 的最大重复值......
  • 力扣 257. 二叉树的所有路径
    257.二叉树的所有路径给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径。叶子节点是指没有子节点的节点。示例1:输入:root=[1......
  • 力扣 129. 求根节点到叶节点数字之和
    129.求根节点到叶节点数字之和给你一个二叉树的根节点 root ,树中每个节点都存放有一个 0 到 9 之间的数字。每条从根节点到叶节点的路径都代表一个数字:例......
  • 力扣-147-对链表进行插入排序
    ListNode*insertionSortList(ListNode*head){ //待排节点需要和它前面的节点比较?单链表怎么比,单链表的反向遍历? //只能从头开始找 //还要手写链表的交换? if(!he......
  • 力扣 124. 二叉树中的最大路径和 [1.0,2.0]
    124.二叉树中的最大路径和路径 被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 ......
  • AcWing 1221 四平方和
    \(AcWing\)\(1221\).四平方和+自定义排序(重载<)+二分一、题目大意四平方和定理,又称为拉格朗日定理:每个正整数都可以表示为至多\(4\)如果把\(0\)包括进去,就正好可以表......
  • 力扣 113. 路径总和 II [dfs,bfs]
    113.路径总和II给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。叶子节点是指没有子节......
  • 代码随想录算法训练营第二天| 977.有序数组的平方 ,209.长度最小的子数组 ,59.螺旋矩阵I
    977.有序数组的平方:https://leetcode.cn/problems/squares-of-a-sorted-array/心得:周末再写。。。publicclassSolution{publicstaticvoidmain(String[]arg......