Line data    Source code

       1              : // Copyright (c) 2024 The Authors. All rights reserved.
       2              : //
       3              : // Licensed under the Apache License, Version 2.0 (the "License");
       4              : // you may not use this file except in compliance with the License.
       5              : // You may obtain a copy of the License at
       6              : //
       7              : //      https://www.apache.org/licenses/LICENSE-2.0
       8              : //
       9              : // Unless required by applicable law or agreed to in writing, software
      10              : // distributed under the License is distributed on an "AS IS" BASIS,
      11              : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
      12              : // See the License for the specific language governing permissions and
      13              : // limitations under the License.
      14              : 
      15              : // Authors: liubang (it.liubang@gmail.com)
      16              : 
      17              : #include <climits>
      18              : #include <vector>
      19              : 
      20              : #include <gtest/gtest.h>
      21              : 
      22              : namespace {
      23              : /**
      24              :  * 这是一道典型的完全背包的问题，完全背包跟01背包的区别在于，完全背包中元素可重复
      25              :  * 因此在选择元素的时候，需要遍历寻找最优值
      26              :  *
      27              :  * 设dp[i]表示和为i的完全平方数的最少个数，那么dp[i]的递推公式为 dp[i] =
      28              :  * min(dp[i - 1*1], dp[i - 2 * 2], dp[i - j * j]) + 1; for(j = 1; j*j <= i; ++j)
      29              :  * 其中 j >= 1, j*j <= i;
      30              :  *
      31              :  * 清楚了递推公式，代码就非常简单了。
      32              :  */
      33              : class Solution {
      34              : public:
      35            4 :     int numSquares(int n) {
      36            4 :         std::vector<int> dp(n + 1, 0);
      37           58 :         for (int i = 1; i <= n; ++i) {
      38           54 :             int min = INT_MAX;
      39          172 :             for (int j = 1; j * j <= i; ++j) {
      40          118 :                 min = std::min(min, dp[i - j * j]);
      41              :             }
      42           54 :             dp[i] = min + 1;
      43              :         }
      44            8 :         return dp[n];
      45            4 :     }
      46              : };
      47              : } // namespace
      48              : 
      49            4 : TEST(Leetcode, leetcode) {
      50            1 :     Solution s;
      51            1 :     EXPECT_EQ(3, s.numSquares(12));
      52            1 :     EXPECT_EQ(2, s.numSquares(13));
      53            1 :     EXPECT_EQ(3, s.numSquares(14));
      54            1 :     EXPECT_EQ(4, s.numSquares(15));
      55            1 : }