[LeetCode]Climbing Stairs

DP和递归解法。值得一提的是DP只需要用前两个数，所以不需要开辟数组，constant space。f[i]代表爬到第i个阶梯的时候有多少种方法

• f[i] = f[i - 1] + f[i - 2]
• f[0] = f[1];
• f[1] = f[1];

DP代码如下：

	public class Solution {
	public int climbStairs(int n) {
	if (n <= 0)
	return 0;
	int x = 1;
	int y = 1;
	for (int i = 1; i < n; i++) {
	int z = x + y;
	x = y;
	y = z;
	}
	return y;
	}
	}

view raw climbing stairs.java hosted with ❤ by GitHub