JacobGo！

二刷这道题，其实方法三还可以继续进行优化，后续会把具体算法【解法四】补上

现在说一下大致思路：求出递推公式

f(n)=f(n-1)+f(n-2) ===>f(n)+f(n-1)=2f(n-1)+f(n-2)

[f(n) f(n-1)]=[[1 1][1 0]][f(n-1) f(n-2)]

可以得到递推矩阵

所以该算法的关键点就是：1.需要求出递推矩阵；2.写一个方法，能够实现矩阵相乘

虽然代码量会比其他几个方法大，但是算法复杂度比较低

/*

 * 动态规划解法
 */
public int climbStairs3(int n) {
    if (n <= 0)
        return 0;
    if (n == 1)
        return 1;
    if (n == 2)
        return 2;

    int[][] base = { { 1, 1 }, { 1, 0 } };
    int[][] res = matrixPower(base, n - 2);

    return 2*res[0][0] + res[1][0];
}


/*
 * 求矩阵m的p次方
 */
public int[][] matrixPower(int[][] m, int p) {
    int[][] res = new int[m.length][m[0].length];
    // 把res设为单位矩阵，相当于整数中的1；
    for (int i = 0; i < res.length; i++) {
        res[i][i] = 1;
    }

    int[][] tmp = m;
    for (; p != 0; p >>= 1) {
        if ((p & 1) != 0)
            res = muliMatrix(res, tmp);
        tmp = muliMatrix(tmp, tmp);
    }
    return res;
}

/*
 * 两个矩阵相乘
 */
private int[][] muliMatrix(int[][] m1, int[][] m2) {
    int[][] res = new int[m1.length][m2[0].length];
    for (int i = 0; i < m1.length; i++) {
        for (int j = 0; j < m2[0].length; j++) {
            for (int k = 0; k < m2.length; k++) {
                res[i][j] += m1[i][k] * m2[k][j];
            }
        }
    }
    return res;
}

//包含三种最常用的回答，第一最优，第三最差，
/*

 * 空间复杂度O(1);
 */
public int climbStairs(int n) {
    if (n < 3)
        return n;
    int one_step_before = 2;
    int two_steps_before = 1;
    int all_ways = 0;
    for (int i = 2; i < n; i++) {
        all_ways = one_step_before + two_steps_before;
        two_steps_before = one_step_before;
        one_step_before = all_ways;
    }
    return all_ways;
}
/*
 * 空间复杂度O(n);
 */
public int climbStairs_2(int n) {
    if (n < 3)
        return n;
    int[] res = new int[n + 1];
    res[1] = 1;
    res[2] = 2;
    for (int i = 3; i <= n; i++) {
        res[i] = res[i - 1] + res[i - 2];
    }
    return res[n];
}
/*
 * 方法一：递归 时间复杂度高
 */
public int climbStairs_1(int n) {
    if (n < 1)
        return 0;
    if (n == 1)
        return 1;
    if (n == 2)
        return 2;
    return climbStairs_1(n - 1) + climbStairs_1(n - 2);
}

```

编辑于 2018-01-08 20:29:46 回复(0)

夕一啊

//剑指offer里面出现过。斐波那契，用非递归的方法
class Solution {
public:
    int climbStairs(int n) {
        int f = 1;
        int g = 0;
        while(n--){
            f += g;
            g = f -g;            
        }
        return f;
    }
};

编辑于 2017-06-12 17:07:57 回复(2)

可乐猪

//斐波那契数列
class Solution {
public:
    int climbStairs(int n) {
        //递归方法，时间不够。。。
        /*if (n <= 1) 
            return 1;
        return climbStairs(n-1) + climbStairs(n-2);
        */
        
        //非递归方法，自己在for循环里面模拟递归
        int result = 1, pre = 0;
        for (int i = 1; i <= n; i++) {
            int tmp = result;
            result += pre;
            pre = tmp;
        }
        return result;
    }
};

发表于 2016-09-01 17:49:34 回复(0)

我要吃油泼面

  public class Solution {
    /*  暴力递归  此题超时
    public int climbStairs(int n) {
        if(n == 1)
            return 1;
        if(n == 2)
            return 2;
        return climbStairs(n - 1) + climbStairs(n -2);
    }
    */
    //常规时间复杂度O(n)算法
    public int climbStairs(int n) {
    	if(n == 2)
            return 2;
        if(n == 1)
            return 1;
        int tmp = 0;
        int pre = 1; 
        int res = 2;
        for(int i = 3; i <= n; i++){
      		tmp = res;
            res = res + pre;
            pre = tmp;
        }
        return res;
    }
    /*
    //动态规划   空间和时间复杂度都为O(n)，
    public int climbStairs(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
    */
}

发表于 2017-05-14 16:09:24 回复(2)

输出些什么好

import java.util.*;

public class Solution {
/**
*
* @param n int整型
* @return int整型
*/
//递归，时间复杂高
public int climbStairs1 (int n) {
// write code here

if(n <= 2) return n;

return climbStairs(n-1)+climbStairs(n-2);
}

//动态规划，时间复杂度低
public int climbStairs (int n) {
// write code here
if(n <= 2) return n;

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];
}
return dp[n];
}
}

发表于 2020-09-04 17:29:50 回复(0)

Python

🇮🇹ForzaMilan！

#
# 
# @param n int整型 
# @return int整型
#
class Solution:
    def climbStairs(self , n ):
        # write code here
        if n <= 2:
            return(n)
        else:
            dp = [0 for x in range(n+1)]
            dp[1],dp[2] = 1,2
            for i in range(3,n+1):
                dp[i] = dp[i-1]+dp[i-2]
            return(dp[-1])

发表于 2020-05-26 17:23:43 回复(0)

武培轩

Leetcode#70. Climbing Stairs（爬楼梯）

package DynamicProgramming;

/**
 * 70. Climbing Stairs（爬楼梯）
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 */
public class Solution70 {
    public static void main(String[] args) {
        Solution70 solution70 = new Solution70();
        System.out.println(solution70.climbStairs(3));
    }

    /**
     * 直接用递归
     *
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        } else {
            return climbStairs(n - 1) + climbStairs(n - 2);
        }
    }

    /**
     * 用迭代的方法，用两个变量记录f(n-1) f(n-2)
     *
     * @param n
     * @return
     */
    public int climbStairs_2(int n) {
        int one = 1, two = 2, fN = 0;
        if (n <= 0) {
            return 0;
        } else if (n <= 2) {
            return n;
        } else {
            for (int i = 3; i <= n; i++) {
                fN = one + two;
                one = two;
                two = fN;
            }
            return fN;
        }
    }
}

发表于 2018-09-12 16:26:17 回复(0)

anyco

public class Solution {
    public int climbStairs(int n) {
        if(n<=2) return n;
        int[] a = new int[n+1];
        a[1] = 1;
        a[2] = 2;
        for(int i=3; i<=n; i++) {
            a[i] = a[i-1] + a[i-2];
        }
        return a[n];
    }
}

发表于 2017-11-21 20:22:31 回复(0)

C/C++

华科平凡

C++ solution


class Solution {
public:
    int climbStairs(int n) {
        vector<int> res(n + 1, 0);
        res[0] = 1;
        res[1] = 1;
        for (int i = 2; i <= n; ++i) {
            res[i] = res[i - 1] + res[i-2];
        }
        return res[n];
    }
};

发表于 2017-10-31 15:03:01 回复(0)

nomico271

动态规划，将原问题拆开成若干子问题，保存子问题答案。

public class Solution {
    public int climbStairs(int n) {
        if(n == 1) return 1;
        if(n == 2) return 2;
        
        int a = 2;
        int b = 1;
        int result = 0;
        for(int i = 3; i <= n; i++){
            result  = a + b;
            b = a;
            a = result ;
        }
        return result ;
    }
}

发表于 2017-07-30 22:13:18 回复(0)

Java

詆調壹點

public int climbStairs(int n) {
		int[] dp = new int[n + 1];
		dp[0] = 1;
		dp[1] = 1;
		for (int i = 2; i < dp.length; i ++ ) {
			dp[i] = dp[i - 1] + dp[i - 2];
		}
		return dp[n];
	}

发表于 2016-11-06 14:29:18 回复(0)

NothingCoder

//本质为斐波拉契数列
	//1.假设当有n个台阶时假设有f(n)种走法。
	//2.青蛙最后一步要么跨1个台阶要么跨2个台阶。
	//3.当最后一步跨1个台阶时即之前有n-1个台阶，根据1的假设即n-1个台阶有f(n-1)种走法。
	//4. 当最后一步跨2个台阶时即之前有n-2个台阶，根据1的假设即n-2个台阶有f(n-2 )种走法。
	//5.显然n个台阶的走法等于前两种情况的走法之和即f(n)=f(n-1)+f(n-2)。
    public int climbStairs(int n) {
		if(n<0) return -1;
		if(n ==0 ||n==1 || n==2) return n;
		
		int first = 1,second = 2,third = 0;
		for(int i = 3;i<=n;i++){
			third = first + second;
			first = second;
			second = third;
		}
		return third;
	}

编辑于 2016-07-14 23:00:15 回复(0)

C++

好菜啊我

/*
思路：动态规划

和斐波那契数列相同的思路。

第三节楼梯有两种抵达方式：
1.从第1节直接走两步
2.从第2节走一步

因此爬到第3节的方法数变成了：爬到第一节+爬到第二节的方法数



状态定义：
f0：第i-2节楼梯的方法数
f1：第i-1节楼梯的方法数
f2：第i节楼梯的方法数

状态转移方程：
f2 = f1 + f0;
f0 = f1;
f1 = f2;

*/
class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @return int整型
     */
    int climbStairs(int n) {
        //前三层的可以直接算出来，因此可以直接返回
        if(n <= 3){
            return n;
        }

        int f1 = 1;
        int f2 = 2;

        int f3;

        //利用动态规划计算
        for(int i=3;i<=n;i++){
            f3 = f1+f2;
            f1 = f2;
            f2 = f3;
        }

        return f3;
    }
};

发表于 2023-04-10 17:11:29 回复(0)

JAVA开发区

// 动态规划问题，跟斐波那契数列是一样的，用dp数组就可以求出
public class Solution {
    public int climbStairs (int n) {
        int dp[] = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2;i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
}

发表于 2022-11-10 09:49:12 回复(0)

诗悦网络内推_有问必答

Erlang动态规划拆分情况
解题思路

因为每次只能爬1或2个台阶, 从1个2个台阶开始推断, 并将问题n阶台阶拆解为求解到达n-1阶台阶以及n-2阶台阶的总和, 过程中缓存已记录阶数对应的数据

代码

-spec climb_stairs(N :: integer()) -> integer().
climb_stairs(N) when N =< 2 ->
    N;
climb_stairs(N) ->
    do_climb_stairs(3, #{stairs => N, 1 => 1, 2 => 2}).

do_climb_stairs(N, Args = #{stairs := Stairs}) when N < Stairs ->
    Sum = maps:get(N - 1, Args) + maps:get(N - 2, Args),
    do_climb_stairs(N + 1, Args#{N => Sum});
do_climb_stairs(N, Args) ->
    maps:get(N - 1, Args) + maps:get(N - 2, Args).

发表于 2021-11-02 13:36:53 回复(0)

C++

小雨嘻嘻

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @return int整型
     */
    int climbStairs(int n) {
        // write code here
        //f(n)=f(n-1)+f(n-2),f(0)=1,f(1)=1,f(2)=2,f(3)=3
        //动态规划，非递归
        if(n==0||n==1) return 1;
        int a=1,b=1,c;
        for(int i=2;i<=n;i++){
            c=a+b;
            a=b;
            b=c;
        }
        return c;
    }
};

发表于 2021-10-24 10:02:34 回复(0)

sid233

会不会很low

def climbStairs(self, n):
    f1, f2 = 0, 1
    for _ in range(0, n):
        f1, f2 = f2, f1 + f2
    return f2

发表于 2021-08-21 01:08:52 回复(0)

何曾有丶飞的梦想

快速幂+矩阵乘法

class Solution {
public:
    #include <cstring>
    void mul(int c[][2], int a[][2], int b[][2]){
        static int tmp[2][2] = {0, 0, 0, 0};
        memset(tmp, 0, sizeof tmp);
        for(int i = 0; i < 2; ++ i)
            for(int j = 0; j < 2; ++ j)
                for(int k = 0; k < 2; ++ k)
                    tmp[i][j] += a[i][k] * b[k][j];
        memcpy(c, tmp, sizeof tmp);
    }
    void qmi(int a[][2], int b[][2], int k){
        while(k){
            if(k & 1) mul(a, a, b);
            mul(b, b, b);
            k >>= 1;
        }
    }
    int climbStairs(int n) {
        int F[2][2] = {1, 1, 0, 0};
        int a[2][2] = {1, 1,1, 0};
        qmi(F, a, n - 1);
        return F[0][0];
    }
};

发表于 2021-06-25 14:27:09 回复(0)

C/C++

codewind

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @return int整型
     */
    int climbStairs(int n) {
        // write code here
        int dp[1000];
        dp[1] = 1,dp[2] = 2;
        for(int i=3;i<=n;++i) dp[i] = dp[i-1]+dp[i-2];
        return dp[n];
    }
};

发表于 2021-04-11 17:34:31 回复(0)

Java

振资

public int climbStairs (int n) {
        // write code here
        // 斐波那契数列
        // 动态规划
        //if (n <= 3) {
        //    return n;
        //}
        //int dp[] = new int[n];
        //dp[0] = 1;
        //dp[1] = 2;
        //dp[2] = 3;
        //for (int i = 2; i < n; i++) {
        //    dp[i] = dp[i - 1] + dp[i - 2];
        //}
        //return dp[n-1];
        
        // 压缩状态
        int a = 0, b = 0, c = 1;
        for (int i = 0; i < n; i++) {
            a = b;
            b = c;
            c = a + b;
        }
        return c;
    }

发表于 2021-04-04 13:23:37 回复(0)

爬楼梯

输入

输出

输入

输出

C++ solution

问题信息

热门推荐

通过挑战的用户

相关试题