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