2020-11-11--数据结构与算法-15(动态规划篇2)

1.斐波那契问题比较自上而下 和 自下而上

public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(fibonacci(12));
        System.out.println(fibonacci1(12));
        System.out.println(fibonacci2(12));
    }

    public static int fibonacci(int number) {
        //递归实现
        if (number == 1 || number == 2) {
            return 1;
        } else {
            return fibonacci(number - 1) + fibonacci(number - 2);
        }
    }

    //动态规划1
    public static int fibonacci1(int number) {
        //考虑建立一个数组存放所有的状态
        //注意容量和索引的不同
        int[] dp = new int[number];
        //初始化0 ,1
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i < number; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[number-1];
    }

    //动态规划,考虑压缩
    public static int fibonacci2(int number) {
        //两个变量接收遍历的值
        int first = 1;
        int second = 1;
        for (int i = 3; i <= number; i++) {
              int tmp = first + second;
              first = second;
              second = tmp;
        }
        return  second;
    }
}