动态规划--斐波那契数列问题

S90517-115953.jpg

import java.util.Arrays;


class Solution {
    //使用记忆搜索, 将产生的结果暂时保存
    public static int fib(int n) {
        int[] memo = new int[n + 1];
        Arrays.fill(memo, -1);

        return fib(n, memo);
    }

    public static int fib(int n, int[] memory) {
        if (n == 0) {
            return 0;
        }

        if (n == 1) {
            return 1;
        }

        if (memory[n] == -1) {
            memory[n] = fib(n - 1, memory) + fib(n - 2, memory);
        }

        return memory[n];
    }

    public static void main(String[] args) {
        for (int i = 10; i < 1000; i += 10) {
            totalTime(i);
        }
    }

    public static int fibNomal(int n) {
        int[] memo = new int[n + 1];
        memo[0] = 0;
        memo[1] = 1;

        for (int i = 2; i < n + 1; i++) {
            memo[i] = memo[i - 1] + memo[i - 2];
        }
        
        return memo[n];
    }

    public static void totalTime(int num) {
        double start = System.nanoTime();
        fibNomal(num);
        double end = System.nanoTime();

        System.out.println(num + " total time: " + (end - start) / 1000000);
    }
}

![ S90517-120826.jpg S90517-121136.jpg S90517-121258.jpg
S90517-122048.jpg S90517-122424.jpg S90517-122455.jpg S90517-122524.jpg S90517-122645.jpg S90517-180745.jpg S90518-113531.jpg S90518-113559.jpg S90518-113830.jpg S90518-114035.jpg S90518-114233.jpg S90518-114407.jpg S90518-114816.jpg S90521-161024.jpg S90521-161108.jpg S90521-161805.jpg S90521-163301.jpg S90521-163347.jpg S90521-163506.jpg S90521-163537.jpg S90521-163548.jpg S90521-164036.jpg