Line data    Source code

       1              : // Copyright (c) 2022 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: 2022/01/17 14:50
      17              : 
      18              : #include <gtest/gtest.h>
      19              : 
      20              : #include <vector>
      21              : 
      22              : namespace {
      23              : class Solution {
      24              : public:
      25            3 :     int uniquePaths(int m, int n) {
      26            3 :         std::vector<std::vector<int>> dp(m, std::vector<int>(n, 0));
      27           19 :         for (int i = 0; i < m; ++i) {
      28          113 :             for (int j = 0; j < n; ++j) {
      29           97 :                 dp[i][j] = (i == 0 || j == 0) ? 1 : dp[i - 1][j] + dp[i][j - 1];
      30              :             }
      31              :         }
      32            6 :         return dp[m - 1][n - 1];
      33            3 :     }
      34              : };
      35              : } // namespace
      36              : 
      37            4 : TEST(Leetcode, unique_paths) {
      38            1 :     Solution s;
      39            1 :     EXPECT_EQ(28, s.uniquePaths(3, 7));
      40            1 :     EXPECT_EQ(3, s.uniquePaths(3, 2));
      41            1 :     EXPECT_EQ(5005, s.uniquePaths(10, 7));
      42            1 : }