|
题目描述：
- 假设你正在爬楼梯。需要 n?阶你才能到达楼顶。
- 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
PS：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. ?1 阶 + 1 阶
2. ?2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. ?1 阶 + 1 阶 + 1 阶
2. ?1 阶 + 2 阶
3. ?2 阶 + 1 阶
?题解：
- 这道题采用动态规划主要是因为这是第一次接触动态规划问题，这道题也可以用分治法去做，但是还是选择用动态规划去解决。
- 动态规划是解决重复计算，自底向上去分解问题。
- 假设现在在初始位置，并准备爬上第一阶，那么就只有一种方法，那就是爬一次一阶。
- 准备爬第二阶，那就是两种方法，一次爬两次一阶和一次性爬两阶。
- 重点来了，爬上第三阶的前提，你可以在第一阶和第二阶，因为你一次性只能爬一或者二阶，不可能在初始位置一下子爬到第三阶。那么在第一阶爬到第三阶，就是相当于在初始位置爬到第二阶，方法个数是一样的，都是两种，在第二阶爬上第三阶就是相当于在初始位置爬到第一阶，那么爬到第三阶的方法就可以分解为求爬到第二阶和爬到第一阶的方法个数总和。
- 爬到第四阶也只能是在第二阶或者第三阶，那么就是可以分解为求爬到第二阶和爬到第三阶方法个数总和，而爬到第三阶又可以分解为爬到第一阶和第二阶方法个数总和。
这里设爬到第n阶的函数为f(n) = f(n-1) + f(n-2)
那么做一个总的求解过程：
f(1) = 1
f(2) = 2
f(3) = f(2) + f(1)
f(4) = f(3) + f(2)
……
……
f(n) = f(n-1) + f(n-2)
PS:这个和斐波那契数列差不多求法，可以先求好保存到数组中，最后直接调用返回对应的方法总数即可。
?代码：
class Solution {
public:
int climbStairs(int n) {
return recursion(n);
}
int recursion(int n) {
int pwd[100];
if(n<=0) return 0;
pwd[1] = 1;
pwd[2] = 2;
for(int i = 3;i<=n;i++) {
pwd[i] = pwd[i-1] + pwd[i-2];
}
return pwd[n];
}
};
?
|