8、动态规划基础

lidong / 2023-05-25 / 原文

内容来自刘宇波老师玩转算法面试

1、斐波那契数列

1.1、Fibonacci Sequence

public class Fib {

    private static int num;

    /**
     * 斐波那契数列 Fibonacci Sequence
     * F(0) = 0, F(1) = 1, F(n) = F(n - 1) + F(n - 2)
     */
    public static int fib(int n) {
        num++;
        if (n <= 1) return n;
        return fib(n - 1) + fib(n - 2);
    }

    private static void testTime(int n) {
        num = 0;

        double startTime = System.nanoTime();
        System.out.println("fib(" + n + ") = " + fib(n));
        double endTime = System.nanoTime();

        double time = (endTime - startTime) / 1e9;
        System.out.println("Time = " + time + " s");
        System.out.println("run function fib() " + num + " times");
    }

    public static void main(String[] args) {
        int n = 40;
        testTime(n);
    }
}

// fib(40) = 102334155
// Time = 0.3558361 s
// run function fib() 331160281 times

1.2、Fibonacci Sequence 的重复计算

1.3、自上而下解决问题「记忆化搜索」

/**
 * 记忆化搜索
 * 自上而下解决问题
 */
public class Fib {

    private static int num;
    private static List<Integer> memo; // memo[n] = fib(n)

    /**
     * <p>斐波那契数列 Fibonacci Sequence
     * <p>F(0) = 0, F(1) = 1, F(n) = F(n - 1) + F(n - 2)
     */
    public static int fib(int n) {
        num++;
        if (n <= 1) return n;

        if (n < memo.size()) return memo.get(n - 1) + memo.get(n - 2);

        int res = fib(n - 1) + fib(n - 2);
        memo.add(n, res);
        return res;
    }

    private static void testTime(int n) {
        num = 0;
        memo = new ArrayList<>();
        memo.add(0);
        memo.add(1);

        double startTime = System.nanoTime();
        System.out.println("fib(" + n + ") = " + fib(n));
        double endTime = System.nanoTime();

        double time = (endTime - startTime) / 1e9;
        System.out.println("Time = " + time + " s");
        System.out.println("run function fib() " + num + " times");
    }

    public static void main(String[] args) {
        int n = 40;
        testTime(n);
    }
}

// fib(40) = 102334155
// Time = 3.143E-4 s
// run function fib() 79 times

1.4、自下而上解决问题「动态规划」

/**
 * 动态规划
 * 自下而上解决问题
 */
public class Fib {

    /**
     * 斐波那契数列 Fibonacci Sequence
     * F(0) = 0, F(1) = 1, F(n) = F(n - 1) + F(n - 2)
     */
    public static int fib(int n) {
        ArrayList<Integer> memo = new ArrayList<>(); // memo[n] = fib(n)
        memo.add(0);
        memo.add(1);

        for (int i = 2; i <= n; i++) {
            memo.add(memo.get(i - 1) + memo.get(i - 2));
        }

        return memo.get(n);
    }

    private static void testTime(int n) {
        double startTime = System.nanoTime();
        System.out.println("fib(" + n + ") = " + fib(n));
        double endTime = System.nanoTime();

        double time = (endTime - startTime) / 1e9;
        System.out.println("Time = " + time + " s");
    }

    public static void main(String[] args) {
        int n = 40;
        testTime(n);
    }
}

// fib(40) = 102334155
// Time = 2.238E-4 s