279. 完全平方数(完全背包)

系统管理员 2023-01-12 13:59 307阅读 0赞

### 解题思路

一个典型的完全背包问题

### 代码

  1. class Solution {
  2. public:
  3.     int numSquares(int n) {
  4.         vector<int> tab;
  5.         for(int i = 1; i <= 100;++i){
  6.             if(pow(i,2) <= n){
  7.                 tab.push_back(pow(i,2));
  8.             }else break;
  9.         }
  10.         vector<int> dp(n+1,1e9);
  11.         dp[0] = 0;
  12.         for(int i = 1; i <= tab.size(); ++i){
  13.             for(int j = tab[i-1]; j <= n; ++j){
  14.                  dp[j] = min(dp[j],dp[j-tab[i-1]]+1);
  15.             }
  16.         }
  17.         return dp[n];
  18.     }
  19. };

发表评论

表情：
评论列表 （有 0 条评论，307人围观）

还没有评论，来说两句吧...

相关阅读

    相关 279. 完全平方数

    给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 给你一个整数 n ，返回和为 n

    心已赠人心已赠人/ 0 赞/ 313 阅读