力扣 279. 完全平方数

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

题目

• 给你一个整数 n ，返回 和为 n 的完全平方数的最少数量
• 完全平方数可以拆解为两个相同数的乘积

思路

• dp 公式，就是从看用哪个完全平方数 1 2 4 9…… 到当前 sum 的数量最少

代码

class Solution {
public:int numSquares(int n) {vector<int> dp(n+1);dp[0] = 0;dp[1] = 1;for (int i = 2; i <= n; i++) {dp[i] = dp[i-1] + 1;for (int j = 2; j * j <= i; j++) {dp[i] = min(dp[i], dp[i - j*j] + 1);}}return dp[n];}
};