关于java:LeetCode070爬楼梯

30次阅读

共计 963 个字符，预计需要花费 3 分钟才能阅读完成。

题目形容：假如你正在爬楼梯。须要 n 阶你能力达到楼顶。

每次你能够爬 1 或 2 个台阶。你有多少种不同的办法能够爬到楼顶呢？

留神：给定 n 是一个正整数。

示例阐明请见 LeetCode 官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

问题解析

典型的斐波那契数列，因为到第 n 个台阶有 2 种走法，要么是从第 n - 1 个台阶下来，要么是从第 n - 2 个台阶下来，所以到第 n 个台阶的走法总数等于第 n - 1 个台阶的走法加上第 n - 2 个台阶的走法。

解法一：递归

递归调用同一个办法，首先如果 n 为 1 或者 2 的时候间接返回 n；如果 n 大于 2 的时候则递归调用该办法即 f(n) = f(n - 1) + f(n - 2)。

解法二：迭代

首先如果 n 为 1 或者 2 的时候间接返回 n；如果 n 大于 2 的时候，则记录 2 个之前的值别离为 lastOne 和 lastTwo，则以后的值为这 2 个值的和，而后更新 lastOne 和 lastTwo 的值，直到迭代到 n 为止。

public class LeetCode_070 {
    /**
     * 递归：提交时超出工夫限度了
     *
     * @param n
     * @return
     */
    public static int climbStairs(int n) {if (n == 1 || n == 2) {return n;}
        return climbStairs(n - 1) + climbStairs(n - 2);
    }

    /**
     * 迭代
     *
     * @param n
     * @return
     */
    public static int climbStairs2(int n) {if (n == 1 || n == 2) {return n;}
        int lastOne = 1, lastTwo = 2, result = -1;
        for (int i = 3; i <= n; i++) {
            result = lastOne + lastTwo;
            lastOne = lastTwo;
            lastTwo = result;
        }
        return result;
    }

    public static void main(String[] args) {System.out.println(climbStairs(45));
        System.out.println(climbStairs2(45));
    }
}