Climbing Stairs
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?
简单题目,相当于fibonacci数列问题,难点就是要会思维转换,转换成为递归求解问题,多训练就可以了。
所以这种类型的题目相对于没有形成递归逻辑思维的人来说,应该算是难题。
我的想法是:
每次有两种选择,两种选择之后又是各有两种选择,如此循环,正好是递归求解的问题。
写成递归程序其实非常简单,三个语句就可以:
int climbStairsRecur(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return climbStairsRecur(n-1) + climbStairsRecur(n-2);
}
但是递归程序一般都是太慢了,因为像Fibonacci问题一样,重复计算了很多分支,我们使用动态规划法填表,提高效率,程序也很简单,如下:
int climbStairs(int n)
{
vector<int> res(n+1);
res[0] = 1;
res[1] = 1;
for (int i = 2; i <= n; i++)
{
res[i] = res[i-1] + res[i-2];
}
return res[n];
}
动态规划法用熟了,高手就需要节省空间了,如下:
int climbStairs2(int n)
{
vector<int> res(3);
res[0] = 1;
res[1] = 1;
for (int i = 2; i <= n; i++)
{
res[i%3] = res[(i-1)%3] + res[(i-2)%3];
}
return res[n%3];
}
当然,不使用上面的数组也是可以的,直接使用三个变量保存结果也是一样的。
//2014-2-10 update
int climbStairs(int n)
{
if (n < 4) return n;
int a = 2, b = 3, c = 5;
for (int i = 5; i <= n; i++)
{
a = c;
c = b+c;
b = a;
}
return c;
}
分享到:
相关推荐
javascript javascript_leetcode面试题解递归与回溯问题之第59题递归矩阵_题解
LeetCode 英文版 递归的教程,只把非会员的部分摘录了下来,没有会员不对。
javascript javascript_leetcode面试题解递归与回溯问题之第560题和为K的子数组_题解
javascript javascript_leetcode面试题解递归与回溯问题之第78题子集_题解
javascript javascript_leetcode面试题解递归与回溯问题之第46题全排列_题解
javascript javascript_leetcode面试题解递归与回溯问题之第47题全排列_题解
javascript javascript_leetcode面试题解递归与回溯问题之第37题解数独_题解
javascript javascript_leetcode面试题解递归与回溯问题之第77题组合_题解
javascript javascript_leetcode面试题解递归与回溯问题之第1219题黄金矿工_题解
javascript javascript_leetcode面试题解递归与回溯问题之第1079题活字印刷_题解
javascript javascript_leetcode面试题解递归与回溯问题之第51题N皇后_题解
javascript javascript_leetcode面试题解递归与回溯问题之第90题子集II_题解
javascript javascript_leetcode面试题解递归与回溯问题之第212题单词搜索_题解
javascript javascript_leetcode面试题解递归与回溯问题之第1291题顺次数_题解
javascript javascript_leetcode面试题解递归与回溯问题之第54题螺旋矩阵_题解
javascript javascript_leetcode面试题解递归与回溯问题之第401题二进制手表_题解
javascript javascript_leetcode面试题解递归与回溯问题之第8第9题括号_题解
javascript javascript_leetcode面试题解递归与回溯问题之第73题矩阵置零_题解
javascript javascript_leetcode面试题解递归与回溯问题之第93题复原ip地址_题解
python 数据结构 算法 LeetCode 牛客 面试 编程之美 动态规划 字典树 快速排序 树 字符串 数组 链表 全排列 堆排序 位运算 大数相加