279. 完全平方数(完全背包) 系统管理员 2023-01-12 13:59 129阅读 0赞 \#\#\# 解题思路 一个典型的完全背包问题 \#\#\# 代码 class Solution { public: int numSquares(int n) { vector<int> tab; for(int i = 1; i <= 100;++i){ if(pow(i,2) <= n){ tab.push_back(pow(i,2)); }else break; } vector<int> dp(n+1,1e9); dp[0] = 0; for(int i = 1; i <= tab.size(); ++i){ for(int j = tab[i-1]; j <= n; ++j){ dp[j] = min(dp[j],dp[j-tab[i-1]]+1); } } return dp[n]; } };
还没有评论,来说两句吧...