leetcode 70 : Climbing Stairs

今天享受一下新换的 markdown 带来的代码编辑体验。先随便做一道leetcode上的简单题自我爽一下,接下来做一道中等难度的题。

题目:

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?

Example:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

自己的想法:

这道题虽然比较简单,但是它体现出来递归的两种解法,从上而下和从下而上这两种。由此可以延伸到动态规划,只要是能用递归解决的问题,动态规划都没有问题。后面写一个递归到动态规划的案例。

Answer:

class Solution {
    public int climbStairs(int n) {
        int f0 = 1;
        int f1 = 1;
        for(int i = 2; i <= n; i++) {
            int temp = f1;
            f1 = f0 + f1;
            f0 = temp;
        }
        return f1;
    }
}

说点什么

avatar
  Subscribe  
提醒

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部