斐波那契数列

/**
 * 递归， 复杂度太高
 *
 * @param args
 */
public static void method1(String[] args) {
    Scanner in = new Scanner(System.in);
    int num = in.nextInt();
    int[] dp = new int[num + 1];
    dp[1] = 1;
    dp[2] = 1;
    for (int i = 3; i <= num; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    System.out.println(dp[num]);
}


/**
 * 通过上面代码我们可以看到当前值只和数组的前两个值有关，
 * 在往前面的就无关了，所以我们没必要申请一个数组，
 * 直接使用两个变量即可，这样空间复杂度就满足要求了
 *
 * @param args
 */
public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int num = in.nextInt();
    int first = 1;
    int second = 1;
    //一个变量保存second值，因为当前值只有前面两个值相关，降低了空间复杂度
    int temp;
    for (int i = 3; i <= num; i++) {
        //先把变量second保存起来
        temp = second;
        second = first + second;
        first = temp;
    }
    System.out.println(second);
}