leecode 解题总结：70. Climbing Stairs

#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
/*
问题:
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?

Note: Given n will be a positive integer.

分析:n个台阶的楼梯，每次只允许爬一个或者两个，问总共有多少种方式。
这个是动态规划
设dp[i]表示到达第i层台阶的方式，
则dp[i] = dp[i-1] + dp[i-2]
边界:dp[1] = 1,dp[2]=2
目标：dp[n]
dp[3]
1,1,1
2,1
1,2
所以dp[3]共有3种
输入:
1
2
3
输出:
1
2
3
*/

class Solution {
public:
    int climbStairs(int n) {
		if(n <= 0)
		{
			return 0;
		}
		if(n <= 2)
		{
			return n;
		}
        vector<int> steps(n + 1 , 0);
		//初始化边界值
		steps.at(1) = 1;
		steps.at(2) = 2;
		for(int i = 3 ; i <= n ; i++)
		{
			steps.at(i) = steps.at(i-1) + steps.at(i-2);
		}
		return steps.at(n);
    }
};

void process()
{
	 int num;
	 Solution solution;
	 while(cin >> num )
	 {
		 int result = solution.climbStairs(num);
		 cout << result << endl;
	 }
}

int main(int argc , char* argv[])
{
	process();
	getchar();
	return 0;
}