C
c++ leetcode climbing stairs DP solution(Top-down and bottom-up)
데브웅
2021. 7. 24. 19:41
Top-down code >>
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public:
vector<int> stairVector{ 1,2 };
int climbStairs(int n) {
if (n == 1)
return 1;
if (n == 2)
return 2;
int sSize = (int)stairVector.size();
if (sSize > n)
return stairVector[n-1];
else
{
int ans = climbStairs(n-1) + climbStairs(n-2);
stairVector.push_back(ans);
return ans;
}
}
};
|
Bottom-up code >>
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
vector<int> stairVector{0, 1,2 };
int climbStairs(int n) {
if (n == 1)
return 1;
if (n == 2)
return 2;
for (int i = 3; i <= n; i++)
{
stairVector.push_back(stairVector[i - 1] + stairVector[i - 2]);
}
return stairVector[n];
}
};
|