Dynamic-Programming

前言

The quote “Those who forget history are condemned to repeat it” is attributed to the American philosopher George Santayana and it can be accurately quoted as “Those who cannot remember the past are condemned to repeat it” as stated in his work, The Life of Reason: Reason in Common Sense.

“那些忘记历史的人注定重蹈覆辙”这句话出自美国哲学家乔治·桑塔亚那之手，准确地说，这句话可以被引用为他在《理性的生活:常识中的理性》一书中所说的“那些不记得过去的人注定重蹈覆辙”。 “Those who cannot remember the past are condemned to repeat it” 这句话忘记是在哪里看到的了,但是我觉得用在动态规划这个章节,真的很合适!

引入

我们可以先来看一个简单的例子,我们之前用递归的方法来求解斐波那契的第n项

1) Fibonacci

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Fibonacci {
 
    public static int fibonacci(int n){
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        int x = fibonacci(n-1);
        int y = fibonacci(n-2);
        return x+y;
    }
}

image-20250807184526767

重复计算了非常多的数据.

后来我们想要用记忆法来优化:

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
/**
     * <h3>使用 Memoization(记忆法, 也称备忘录) 改进</h3>
     *
     * @param n 第 n 项
     * @return 第 n 项的值
     */
    public static int fibonacci(int n) {
        int[] cache = new int[n + 1];
        Arrays.fill(cache, -1); // [-1,-1,-1,-1,-1,-1]
        cache[0] = 0;
        cache[1] = 1; // [0,1,-1,-1,-1,-1]
        return f(n, cache);
    }
 
    // f(3) => 5
    // f(4) => 9
    // f(5) => 15
    //         2*f(n+1) - 1
    private static int f(int n, int[] cache) {
        /*if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }*/
        if (cache[n] != -1) {
            return cache[n];
        }
 
        int x = f(n - 1, cache);
        int y = f(n - 2, cache);
        cache[n] = x + y; // // [0,1,?,-1,-1,-1] 存入数组
        return cache[n];
    }

动态规划也是对递归过程进行改进,只是它是从另外一种方向进行改进,避免重复计算

image-20250807184758795

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
49
50
51
52
53
54
/**
 * 求斐波那契数列的第n项（动态规划）
 */
public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(fibonacci2(13));
    }
    /*
        要点1：
            从已知子问题的解，推导出当前问题的解
            推导过程可以表达为一个数学公式
        要点2：
            用一维或二维数组来保存之前的计算结果（可以进一步优化）
        Dynamic-Programming - 由 Bellman 提出
        动态     编程
            Programming - 在这里指用数学方法来根据子问题求解当前问题（通俗理解就是找到递推公式）
            Dynamic     - 指缓存上一步结果，根据上一步结果计算当前结果（多阶段进行）
        合在一起：
            找出递归公式，将当前问题分解成子问题，分阶段进行求解。
            求解过程中缓存子问题的解，避免重复计算。
     */
    public static int fibonacci2(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int a = 0;
        int b = 1;
        for (int i = 2; i <= n ; i++) {
            int c = b + a;
            a = b;
            b = c;
        }
        return b;
    }
 
    public static int fibonacci(int n) {
        int[] dp = new int[n + 1]; // 用来缓存结果
        if (n == 0) {
            dp[0] = 0;
            return 0;
        }
        if (n == 1) {
            dp[1] = 1;
            return 1;
        }
        for (int i = 2; i <= n ; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

2) [最短路径] - Bellman-Ford

image-20250808065626366

假设要求v1–>v4的最短距离是多少?

image-20250808065654429

分析:

/*
f(v) 用来表示从起点出发，到达 v 这个顶点的最短距离
初始时
f(v) = 0 当 v==起点 时
f(v) = ∞ 当 v!=起点 时

        之后
        新           旧     所有from
        f(to) = min(f(to), f(from) + from.weight)

        from 从哪来
        to   到哪去

        f(v4) = min( ∞, f(v3) + 11 ) = 20
        f(v4) = min( 20, f(v2) + 15 ) = 20


        v1  v2  v3  v4  v5  v6
        0   ∞   ∞   ∞   ∞   ∞
        0   7   9   ∞   ∞   14  第一轮
        0   7   9   20  23  11  第二轮
        0   7   9   20  20  11  第三轮
        0   7   9   20  20  11  第四轮
        0   7   9   20  20  11  第五轮

 */