July 28, 2015
Problem statement:
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?
The problem is most popular question in the algorithm, so I do
like to spend time to find out all sorts of solution, and get myself
comfortable to all kinds of ideas, and figure out which one is best, and all
concerns we can have in the discussion of climbing stairs:
1. Recursion solution vs. DP problem solution (Dynamic
Programming solution)
2. Time complexity solution: O(2^n) vs O(n) solution
3. The space O(N) vs O(1), in other words: array of N or 2
variable, and another tmp variable
4. The base case discussion: f(0) = 1 or f(0) =1, math question?
5. Math formula - closed form solution vs DP problem solution
6. Use Memoization DP vs. no memoization DP
7. Programming skills, how to make code easy to follow, more readable, more abstract.
6. Use Memoization DP vs. no memoization DP
7. Programming skills, how to make code easy to follow, more readable, more abstract.
The investment of time on the problem is well done. Go over 16 implementation one by one using C# programming language.
C# code:
其实, 我觉得题目越容易, 越值得投入时间去学习; 看看大家有没有不同的理解, 打开思路; 如果自己没有训练过这道题, 可能会紧张; 即使训练过, 但是, 有的想法, 可能自己从来没有思考过, 一时还不能判断好坏, 但是, 多看网上的博客, 向每一个人取取经. 谦虚, 才能有提高.
我编网站后台, C#程序自己写; 自己训练的题目太少; 这次选择用Leetcode来提高C#编程, 又可以提高算法和数据结构的知识, 网站后台靠平时训练.
January 3, 2016
Review the leetcode question 70, climbing stairs.
Read the blog:
http://blog.csdn.net/kenden23/article/details/17377869http://yucoding.blogspot.ca/2012/12/leetcode-question-15-climbing-stairs.html
http://www.cnblogs.com/springfor/p/3886576.html
http://www.cnblogs.com/springfor/p/3886576.html
http://siddontang.gitbooks.io/leetcode-solution/content/dynamic_programming/climbing_stairs.html
https://github.com/zwxxx/LeetCode/blob/master/Climbing_Stairs.cpp
