70. Climbing Stairs QuestionEditorial Solution

You are climbing a stair case. It takes n steps 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;
}