Re: [閒聊] 每日LeetCode
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：
----------------------------------------
class Solution {
public int numSquares(int n) {
int[] dp = new int[n + 1];
for (int i = 0; i <= n; i++) {
dp[i] = i;
for (int j = 1; i >= j*j; j++) {
dp[i] = Math.min(dp[i], dp[i - j*j] + 1);
}
}
return dp[n];
}
}
----------------------------------------
https://i.imgur.com/Kx3qqfz.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.231.28.191 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1669088553.A.254.html
推
11/22 11:43,
3年前
, 1F
11/22 11:43, 1F
推
11/22 11:44,
3年前
, 2F
11/22 11:44, 2F
推
11/22 11:45,
3年前
, 3F
11/22 11:45, 3F
※ 編輯: Rushia (36.231.28.191 臺灣), 11/22/2022 11:49:53
推
11/22 11:48,
3年前
, 4F
11/22 11:48, 4F
推
11/22 16:27,
3年前
, 5F
11/22 16:27, 5F
討論串 (同標題文章)
完整討論串 (本文為第 113 之 719 篇)：