Line data    Source code

       1              : // Copyright (c) 2023 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              : // Created: 2023/04/17 13:45
      17              : 
      18              : #include <climits>
      19              : #include <vector>
      20              : 
      21              : #include <gtest/gtest.h>
      22              : 
      23              : namespace {
      24              : /**
      25              :  * 这是一道典型的完全背包的问题，完全背包跟01背包的区别在于，完全背包中元素可重复
      26              :  * 因此在选择元素的时候，需要遍历寻找最优值
      27              :  *
      28              :  * 设dp[i]表示和为i的完全平方数的最少个数，那么dp[i]的递推公式为 dp[i] =
      29              :  * min(dp[i - 1*1], dp[i - 2 * 2], dp[i - j * j]) + 1; for(j = 1; j*j <= i; ++j)
      30              :  * 其中 j >= 1, j*j <= i;
      31              :  *
      32              :  * 清楚了递推公式，代码就非常简单了。
      33              :  */
      34              : class Solution {
      35              : public:
      36            4 :     int numSquares(int n) {
      37            4 :         std::vector<int> dp(n + 1, 0);
      38           58 :         for (int i = 1; i <= n; ++i) {
      39           54 :             int min = INT_MAX;
      40          172 :             for (int j = 1; j * j <= i; ++j) {
      41          118 :                 min = std::min(min, dp[i - j * j]);
      42              :             }
      43           54 :             dp[i] = min + 1;
      44              :         }
      45            8 :         return dp[n];
      46            4 :     }
      47              : };
      48              : } // namespace
      49              : 
      50            4 : TEST(Leetcode, leetcode) {
      51            1 :     Solution s;
      52            1 :     EXPECT_EQ(3, s.numSquares(12));
      53            1 :     EXPECT_EQ(2, s.numSquares(13));
      54            1 :     EXPECT_EQ(3, s.numSquares(14));
      55            1 :     EXPECT_EQ(4, s.numSquares(15));
      56            1 : }