这题和前面 DP1 斐波那契数列基本上是一样的,不同的是,这里斐波那契数列的起始项是1,2,3,5,8,我们把它改一下即可

解法一

题中要求的是 空间复杂度 O(1) ,很明显使用递归是行不通的,我们先改成非递归的看一下(这种复杂度也是不行的,我们先看一下代码)

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        if(num==1||num==2){
            System.out.println(num);
            return ;
        }
        int[] dp = new int[num + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= num; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        System.out.println(dp[num]);
    }
}

通过上面代码我们可以看到当前值只和数组的前两个值有关,在往前面的就无关了,所以我们没必要申请一个数组,直接使用两个变量即可,这样空间复杂度就满足要求了

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
         if(num==1||num==2){
            System.out.println(num);
            return ;
        }
        int first = 1;
        int second = 2;
        int temp;
        for (int i = 3; i <= num; i++) {
            temp = second;//先把变量second保存起来
            second = first + second;
            first = temp;
        }
        System.out.println(second);
    }
}

解法二

斐波那契数列又称黄金分割数列,他有很多的特性,比如跳台阶,兔子的繁殖等,他的通项公式如下,我们还可以通过公式来计算

alt

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        //这里要注意斐波那契数列的前两项,有的是0,1开头,有的是1,1开头,还有的是1,2开头,根据
        //前两项不同而作调整
        int num = in.nextInt();
        if(num==1||num==2){
            System.out.println(num);
            return ;
        }
        double sqrt5 = Math.sqrt(5);
        double fib = Math.pow((1 + sqrt5) / 2, num + 1) - Math.pow((1 - sqrt5) / 2, num + 1);
        System.out.println((int) Math.round(fib / sqrt5));
    }
}

解法三

因为题中说了n的最大值是40,我们可以把它都列出来

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        int[] fib = {1,
                1,
                2,
                3,
                5,
                8,
                13,
                21,
                34,
                55,
                89,
                144,
                233,
                377,
                610,
                987,
                1597,
                2584,
                4181,
                6765,
                10946,
                17711,
                28657,
                46368,
                75025,
                121393,
                196418,
                317811,
                514229,
                832040,
                1346269,
                2178309,
                3524578,
                5702887,
                9227465,
                14930352,
                24157817,
                39088169,
                63245986,
                102334155};

        System.out.println(fib[num]);
    }
}

我把部分算法题整理成了PDF文档,截止目前总共有1000多页,大家可以下载阅读

链接https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ 提取码:6666

如果觉得有用就给个赞吧,还可以关注我的微信公众号【数据结构和算法】查看更多的详细题解