要成功就做一百题-99

题目名称

爬楼梯问题，斐波拉契数列，泰波拉契数列

描述

第一个是常见的题目，第二个斐波拉契，第三个是斐波拉契的变种，只是参数变成了三个。这里只介绍非递归的方法。由于都是一种类型，解法相似，所以放到一起。

解题思路

都是典型的动态规划问题，每一步都依赖前面的两步或者三步，所以使用中间变量将之前的结果缓存起来，然后累加，得到最终的结果。

代码

    public int climbStairs(int n) {
        if (n <= 3) {
            return n;
        }

        int t2 = 2;
        int t3 = 3;
        int t= t3;
        for (int i = 4; i <= n; i++) {
            t = t2 + t3;
            t2 = t3;
            t3 = t;
        }
        return t;
    }

 public int tribonacci(int n) {
        if(n <= 1){
            return n;
        }

        if(n <= 3){
            return n - 1;
        }

        int x1 = 1,x2 = 1,x3 = 2;
        int t = x3;
        for(int i = 4; i <= n; i++){
            t =  x1 + x2 + x3;
            x1 = x2;
            x2 = x3;
            x3 = t;
        }
        return t;

    }
public int fib2(int n){
        if(n <= 1){
            return n;
        }
        if(n == 2){
            return 1;
        }

        int x1 = 1, x2 = 1;
        int t = 1;
        for(int i = 3; i<= n; i++){
            t = (x1 + x2) % 1000000007;
            x1 = x2;
            x2 = t;
        }
        return t;
    }

斐波拉契一直取到100位，这种情况下是超过了Long型的最大值的，所以这里用了取模操作，保持在整数位（都是加法，单次取模和结果取模是一致的）；当然也可以用java的BigInteger实现，经验证效果一样。

总结

以上就是今天完成的题目，类型都很相似，总体复杂度不是很高，知晓一些套路之后，比较容易完成。感谢阅读~