Leetcode 279. 完全平方数 解题思路及C++实现

两种都是动态规划的方法，但第一种比较暴力和愚蠢，第二种利用了完全平方数。

方法一：无脑动态规划，会超时

解题思路：

利用一维数组存储 n 个整数的结果。

首先要判断 i 是不是 就是一个完全平方数，如果是，那就不用循环遍历后面的状态转移方程了，dp[i] = 1即可。

当 i 不是完全平方数时，状态转移方程为 dp[i] = min(dp[k] + dp[i - k])，找到最小的分割，就得到了最少完全平方数的个数。

但是会出现超时。

 

class Solution { public:int numSquares(int n) {vector<int> dp(n+1, 0);dp[1] = 1;if(n == 1) return dp[n];for(int i = 2; i <= n; i++){//要先判断 i 是不是就是完全平方数int j = 1;bool flag = false;while(j * j <= i){if(j * j == i){dp[i] = 1;flag = true;break;}j++;}if(flag) continue;// n 不是完全平方数int minnum = i;for(int k = 1; k < i/2 + 1; k++){if(dp[k] + dp[i - k] < minnum){minnum = dp[k] + dp[i - k];}}dp[i] = minnum;}return dp[n];} };

 

方法二：

解题思路：

自底向上(自小向大)更新 动态数组 dp。状态转移方程为 dp[i + j * j] = min( dp[i + j * j], dp[i] + 1) 。

举例如下，如果输入的 n = 12，则更新顺序为：

dp[0] --> dp[0 + 1*1] = dp[1] --> dp[0 + 2*2] = dp[4] --> dp[0 + 3*3] = dp[9]

dp[1] --> dp[1 + 1*1] = dp[2] --> dp[1 + 2*2] = dp[5] --> dp[1 + 3*3] = dp[10]

dp[2] --> dp[2 + 1*1] = dp[4] -->   ……

……

 

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

 

 

 

总结

以上是生活随笔为你收集整理的Leetcode 279. 完全平方数 解题思路及C++实现的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。