给定正整数 n找到若干个完全平方数(比如 1, 4, 9, 16, ...)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少
-
首先初始化长度为
n+1
的数组dp
,每个位置都为0
-
如果
n
为0
则结果为0
-
對数组进行遍历,下标为
i
每次都将当前数字先更新为最大的结果,即dp[i]=i
比如i=4
,最坏结果为4=1+1+1+1
即为4
个数字
如果觉得文章不错帮忙点个在看唄
给定正整数 n找到若干个完全平方数(比如 1, 4, 9, 16, ...)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少
首先初始化长度为n+1
的数组dp
,每个位置都为0
如果n
为0
则结果为0
對数组进行遍历,下标为i
每次都将当前数字先更新为最大的结果,即dp[i]=i
比如i=4
,最坏结果为4=1+1+1+1
即为4
个数字
如果觉得文章不错帮忙点个在看唄