Re: [闲聊] 每日LeetCode

楼主: Rushia (みけねこ的鼻屎)   2022-11-22 11:42:30
279. Perfect Squares
给你一个数字n,求出相加等于n的数字之最小数量(每个数字要是完全平方数)。
Example:
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.(最小)
12 = 9 + 1 + 1 + 1
12 = ....
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
思路:
1.这题比较偏数学,可以用动态规划解,dp[i]表示组成数字i的最小数量。
2.因为对于一个任意数字n,他都可以被表示成n个1组成,所以dp的所有元素初始
化为i(最大组成i的完全平方数数量)。
3.然后从数字0开始一个一个的填表,外层循环表示dp的每一格,内层循环表示所
有的平方数(1开始),如果满足小于外层循环的值的时候就比较之前的dp[i],和取
现在的 dp[i -j*j] + 1 哪个小,不断的更新表格。
4.返回dp[n]
Java Code:
作者: Jaka (Jaka)   2022-11-22 11:43:00
大师
作者: wwndbk (黑人问号)   2022-11-22 11:44:00
大师
作者: iamwhoim (偏偏爱上了DJ)   2022-11-22 11:45:00
大师
作者: JerryChungYC (JerryChung)   2022-11-22 11:48:00
大师

Links booklink

Contact Us: admin [ a t ] ucptt.com