**Leetcode 279. Perfect Squares | dp

本文主要是介绍**Leetcode 279. Perfect Squares | dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://leetcode.com/problems/perfect-squares/description/

看到dp题先想递推公式啊，这个题的递推公式还是很容易想的

dp[i] = min(dp[i - j * j] ) + 1

j * j <= i

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

一种优化的做法，就是Static数组是全局变量，上次用过之后，下次调用函数，之前的结果是可以保存的。另外，因为1也是1*1，也就是其实所有的数都能被平方数的和表示。因此有了下面discuss的解法  https://leetcode.com/problems/perfect-squares/discuss/71488/Summary-of-4-different-solutions-(BFS-DP-static-DP-and-mathematics)

class Solution {
public:int numSquares(int n) {if(n <= 0) return n;static vector <int> nums({0});while (nums.size() <= n) {int m = nums.size();int v = INT_MAX;for (int i = 1; i * i <= m; i++) {v = min(v, nums[m - i * i] + 1); }nums.push_back(v);}return nums[n];}
};

这篇关于**Leetcode 279. Perfect Squares | dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---