爬楼梯

167 阅读2分钟

这道题有很多中解法,主要是动态规划解法和基于斐波那契数列解法。

跳台阶问题(剑指Offer)

题目:

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

解法一

解题思想:

  • 假设第一次跳1个台阶,那么后面就需要跳n-1个台阶;假设第一次跳2个台阶,那么后面需要跳n-2个台阶(前提是你>=2),所以推导的递推式是f(n)=f(n-1)+f(n-2)

image.png

package com.zhoujian.solutions.leetcode;
import java.util.Scanner;
/**
 * @author zhoujian123@hotmail.com 2018/8/29 14:59
 */
public class UpStairs {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int i = sc.nextInt();
        int s = steps(i);
        System.out.println(s);
    }

    private static int steps(int n) {
        if (n == 1) {
            return 1;
        }
        //用来存放几种走法
        int[] dp = new int[n + 1];
        dp[1]=1;
        dp[2]=2;
        for (int i = 3; i <=n ; i++) {
            //利用递推式求解
            dp[i]=dp[i-1]+dp[i-2];
        }
        //返回的就是n个台阶的走法
        return dp[n];
    }
}

时间复杂度为O(n),空间复杂度为O(n)。(因为创建了一个数组来存放走的解法)。

解法二

上面的解法使用了数组来存放每个n的解法,基于斐波那契数列可以不使用动态规划,从而省掉了这个空间复杂度。(这要是计算这个数的前两个数,并将计算后的数赋值给firstsecond ,依次循环即可)

package com.zhoujian.solutions.leetcode;

import java.util.Scanner;

/**
 * @author zhoujian123@hotmail.com 2018/8/29 14:59
 */
public class UpStairs {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int i = sc.nextInt();
        int s = steps(i);
        System.out.println(s);
    }

    private static int steps(int n) {
        if (n == 1) {
            return 1;
        }
        int first = 1;
        int second = 2;
        for (int i = 3; i <= n; i++) {
            int third = first + second;
            first = second;
            second = third;
        }
        return second;
    }
}

时间复杂度为O(n),空间复杂度为O(1)。

image.png

70 爬楼梯(LeetCode)

题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 12 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。

示例1:

输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。
1.  1 阶 + 12.  2

示例2:

输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 12.  1 阶 + 23.  2 阶 + 1