动态规划简述；斐波那契数列自顶向下和自底向上

概述

动态规划就是把一个问题分解为若干子问题，把子问题的解累加起来，就是当前问题的值。

斐波那契数列（自顶向下）

一个很好的演示demo，
在进行运算时，要用上备忘录（缓存），不然会有重复计算，速度会很慢

public static void main(String[] args) {
    long n = 1000;
    Map<Long,Long> cache = new HashMap<>();
    StopWatch stopWatch = new StopWatch();

    stopWatch.start();
    System.out.println(calc(n, cache));
    stopWatch.stop();
    System.out.println(stopWatch.getTime() + "毫秒");
}


public static long calc(Long n, Map<Long,Long> cache){

    if(n == 0 || n == 1) return 1;

    if(null != cache.get(n)) return cache.get(n);

    long result = calc(n - 1, cache) + calc(n - 2, cache);
    cache.put(n, result);
    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

捞一张大佬的斐波那契数列分解图

斐波那契数列（自底向上）

意思就是从基础开始计算，直到计算得到目标值

 public static void main(String[] args) {
    StopWatch stopWatch = new StopWatch();
    stopWatch.start();
    System.out.println(calcFloor2Up(5000));
    stopWatch.stop();
    System.out.println(stopWatch.getTime() + "毫秒");
}

public static Long calcFloor2Up(int n){
    long[] dp = new long[n+1];
    dp[0] = 0;
    dp[1] = 1;

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





public static void main(String[] args) {
    StopWatch stopWatch = new StopWatch();
    stopWatch.start();
    System.out.println(calcFloor2UpV2(1000));
    stopWatch.stop();
    System.out.println(stopWatch.getTime() + "毫秒");
}

//更快的版本，空间复杂度O(1)
public static int calcFloor2UpV2(int n){
    if (n == 0 || n == 1) {
        // base case
        return n;
    }
    // 分别代表 dp[i - 1] 和 dp[i - 2]
    int dp_i_1 = 1, dp_i_2 = 0;
    for (int i = 2; i <= n; i++) {
        // dp[i] = dp[i - 1] + dp[i - 2];
        int dp_i = dp_i_1 + dp_i_2;
        // 滚动更新
        dp_i_2 = dp_i_1;
        dp_i_1 = dp_i;
    }
    return dp_i_1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48