70. Climbing Stairs QuestionEditorial Solution
You are climbing a stair case. It takesnsteps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
DFS
对于n = 3的情况:
有3种途径
(1, 1, 1)、(1, 2)、(2, 1)
这里(1,2)与(2,1)是两种。
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <sstream>
#include <string>
#include <algorithm>
#include <bitset>
using namespace std;
class Solution {
public:
void dfs(int n)
{
if (n < 0)
{
return;
}
else if(n == 0)
{
count++;
}
else
{
dfs(n - 1);
dfs(n - 2);
}
}
int climbStairs(int n) {
if (m.count(n))
{
return m[n];
}
else
{
count = 0;
dfs(n);
m[n] = count;
return count;
}
}
private:
int count;
map<int, int>m;
};
int main()
{
Solution s;
for (int i = 1; i <= 20; ++i)
{
cout << i << ":" << s. climbStairs(i) << endl;
}
return 0;
}
1:1
2:2
3:3
4:5
5:8
6:13
7:21
8:34
9:55
10:89
11:144
12:233
13:377
14:610
15:987
16:1597
17:2584
18:4181
19:6765
20:10946
[Finished in 2.0s]
观察规律:
X[i] = X[i - 1] + X[i - 2](i > 2)
那么可以采用记忆化搜索,也就是将中间的结果保存下
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
using namespace std;
class Solution {
public:
Solution()
{
memset(num, 0, sizeof(num));
num[1] = 1;
num[2] = 2;
}
int dfs(int n)
{
if (num[n] != 0)
{
return num[n];
}
return (num[n] = dfs(n - 1) + dfs(n - 2));
}
int climbStairs(int n) {
if (num[n] == 0)
{
dfs(n);
}
return num[n];
}
private:
int num[10000];
};
int main()
{
Solution s;
cout << s.climbStairs(44);
return 0;
}