leetcode 279. Perfect Squares 完全平方數(中等)

一、題目大意

標簽: 動態規劃

https://leetcode.cn/problems/perfect-squares

給你一個整數 n ，返回 和為 n 的完全平方數的最少數量 。

完全平方數 是一個整數，其值等於另一個整數的平方；換句話說，其值等於一個整數自乘的積。例如，1、4、9 和 16 都是完全平方數，而 3 和 11 不是。

示例 1：

輸入：n = 12輸出：3解釋：12 = 4 + 4 + 4

示例 2：

輸入：n = 13輸出：2解釋：13 = 4 + 9

提示：

1 <= n <= 104

二、解題思路

動態規劃，dp[i]錶示i有幾個完全平方數的加和構成，枚舉比i小的完全平方數，狀態轉移方程為dp[i] = min(dp[i-k] + 1) ，k就是完全平方數

三、解題方法

3.1 Java實現

class Solution {
 public int numSquares(int n) {
 // 找小於n的完全平方數
 List<Integer> squares = new ArrayList<>();
 for (int i = 1; i < n + 1; i++) {
 int tmp = i * i;
 if (tmp < n + 1) {
 squares.add(tmp);
 } else {
 break;
 }
 }

 int[] dp = new int[n + 1];
 for (int i = 1; i < n + 1; i++) {
 dp[i] = Integer.MAX_VALUE;
 }
 for (int i = 1; i < n + 1; i++) {
 for (int square : squares) {
 if (i < square) {
 break;
 }
 dp[i] = Math.min(dp[i], dp[i - square] + 1);
 }
 }

 return dp[n];
 }
}


四、總結小記

• 2022/6/21 堅持每天一道leetcode，養成一個習慣