Floyd

Floyd是图的经典算法，可以使用动态规划方法解决。但是真正写图搜索算法时不要用Floyd算法，因为它比Dijkstra较慢。但是Floyd对于算法思想的启发很有研究价值。实用价值、研究价值要辩证看。

图

和树一样，有好多节点，但没有树的规律。树是图的子集。

1. 节点和节点之间可以是连通的也可以是不连通的。

2. 连通的线如果没有方向则称之为无向图，如果有方向则为有向图。

3. 如果有循环，则是有环图；如果没有循环则是无环图。

4. 节点的出度：离开这个节点的线的个数；

5. 节点的入度：进入这个节点的线的个数。

应用：地图算法，搜索、寻路；软件工程中Element Block利用有向无环图进行拓扑排序，根据依赖关系、前置关系进行排序。但是还是没有树的应用范围广。

网络路由选择：OSPF（开放式最短路径优先）中就用到了Dijkstra算法。配置路由表。

术语

1. 逆时针：CCW (Counter Clock Wise)
2. 顺时针：CW (Clock Wise)

计算机处理图实际的数据结构

Floyd - 动态规划思想

从某一点到某一点，选择通路，求最短的路径长度。

第一个参数是始发节点，第二个参数是目的节点。第三个参数是可以参与的节点范围（如果是4，则表示1、2、3、4节点全都可以参与），如果是0的话，表示没有中间节点参与。

比如说：floyd(from, to, n)表示：从节点from走到节点to，节点1到n可以参与。求最短路径长度。

运用背包问题的思想。

1
2
3
4
5
6
7
8

floyd(from, to, n)
    不选择第n节点：floyd(from, to, n - 1)
    选择第n节点：  floyd(from, n, n - 1) + floyd(n, to, n - 1)
    最终结果：min {不选择, 选择}
终止条件：
    （1）没有节点参与时，即n == 0 - 结果值为权重表对应数值(某点直接到某点的距离)
    （2）from == to，到达自身。  - 结果值为0
递归方法的时间复杂度：3^n

递归法

如果不选择节点n，则from到to还需在剩下的n-1节点中走。
如果选择节点n，则问题分解成了from到节点n（确定走n，所以可以少走最后的一个节点，因此是n-1），加上剩下的n到to，需要在n-1个节点中走（因为已经到达了节点n，因此可以少走1个）（至于后半段的节点数为什么不是1？要正确理解参数3的意思，指的是可参与的节点，并不是说必须走n个（多于、少于n都可以））。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

int path[5][5] = {
    { 0,   0,   0,   0,   0 },
    { 0,   0, 100, 100,   1 },
    { 0,   3,   0,  10,   5 },
    { 0, 100,   9,   0, 100 },
    { 0, 100, 100,   4,   0 }
};
int floyd_recur(int from, int to, int n)
{
    if (from == to)return 0;
    if (n == 0)
    {
        return path[from][to];
    }
    int no = floyd_recur(from, to, n - 1);
    int yes = floyd_recur(from, n, n - 1) + floyd_recur(n, to, n - 1);
    return no <= yes ? no : yes;
}

测试

1
2
3
4
5
6

int floyd_recur(int from, int to, int n);
int main()
{
    int shortest = floyd_recur(2, 3, 4); // 8
    return 0;
}

复杂度分析

递归方法的时间复杂度：$3^n$

迭代法

因为有三个参数，所以需要三维数组来进行迭代。$n$的有效取值范围为$[0,4]$，0代表没有节点参与。而$from$和$to$的有效取值范围为$[1,4]$，即0是多余的，数组给出多余的1行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

int shortpath[5][5][5];
int floyd(int from, int to, int n)
{
    // n == 0 时
    // 把path表格复制到第0面
    // 行
    for(int i = 0; i <= n; ++i)
    {
        // 列
        for(int j = 0; j <= n; ++j)
        {
            shortpath[0][i][j] = path[i][j];
        }
    }
    // 每一面的from == to 时，等于0
    for(int k = 1; k <= n; ++k)
    {
        for(int i = 0; i <= n; ++i)
        {
            shortpath[k][i][i] = 0;
        }
    }
    //根据第0面迭代
    // k为对应n的面  i为对应from的行 j为对应to的列
    // shortpath 第一个数为面 第二个数为from 第三个数为to
    for(int k = 1; k <= n; ++k)
    {
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= n; ++j)
            {
                int no = shortpath[k - 1][i][j];
                int yes = shortpath[k - 1][i][k] + shortpath[k - 1][k][j];
                
                shortpath[k][i][j] = no <= yes ? no : yes;
            }
        }
    }
    return shortpath[n][from][to];
}
int main()
{
    int shortest = floyd(2, 3, 4); // 8
    return 0;
}

复杂度分析

$O(n^3)$

各种图算法

BFS、DFS、Dijkstra、Bellman-Ford（BF）、Floyd、Prim和Kruskal 等算法是图论和搜索领域中的核心算法，它们各有用途、适用场景和特性。在面试中，通常会从算法的原理、适用场景、时间复杂度、空间复杂度、以及一些优化细节来考查。因此，了解它们的关联与区别是非常重要的。

1. 遍历算法
   1. DFS
   2. BFS
2. 最短路径算法
   1. Dijkstra（好）
   2. Bellman-Ford（好、使用领域广泛，但是最坏性能差）
   3. Floyd（性能不好）
   4. 拓扑排序
3. 最小生成树算法（连通图的子图）
   1. Prim（不好）
   2. Kruskal（好）

1. 广度（BFS）和深度优先搜索（DFS）

关联

• BFS和DFS都是图搜索算法，用于遍历或搜索图的节点。
• 两者都可以用于无向图和有向图，能够找到可达性，即从一个节点到其他节点的路径。

区别

• BFS：逐层扩展节点，适合寻找最短路径（无权图）。
• DFS：沿路径深入搜索，适合找到所有路径或用于图的拓扑排序和强连通分量等应用。

关键点

• 时间复杂度：O(V + E)，其中V是节点数，E是边数。
• 应用场景：BFS常用于无权最短路径、迷宫等问题；DFS常用于路径搜索、连通分量检测等。

2. Dijkstra算法

关联

• Dijkstra是单源最短路径算法，与BFS类似，都用于路径搜索，但适用于带权图。
• 与Bellman-Ford的区别在于它不能处理负权边。

关键点

• 时间复杂度：$O((V + E) * log V)$（使用优先队列）。
• 适用场景：地图导航、网络路由（OSPF）、带权路径问题。
• 限制：不能处理负权边。面试中可能会询问原因，重点在于算法的贪心性质。

与Floyd算法相比

当我们主要用于搜索图时（搜索单源路径），尽量用Dijkstra算法，因为Floyd太耗时了。

3. Bellman-Ford算法

关联

• 与Dijkstra一样，Bellman-Ford也用于单源最短路径。
• Bellman-Ford与Dijkstra的不同之处在于它可以处理负权边，且可以检测负权环。

关键点

• 时间复杂度：O(V * E)。
• 适用场景：处理负权边的路径问题，如金融图表中的盈亏边。
• 特点：可以检测负权环。面试中可能会问到与Dijkstra的区别以及负权环检测方法。

4. Floyd算法

关联

• Floyd用于多源最短路径问题，与Bellman-Ford和Dijkstra不同，它直接求解图中任意两点间的最短路径。
• 与Prim和Kruskal不同，它不用于生成树，而是直接在邻接矩阵上处理所有对路径的情况。

关键点

• 时间复杂度：O(V^3)。
• 适用场景：计算稠密图中所有节点对的最短路径，尤其是对小规模图的处理。
• 优缺点：算法简单但复杂度较高；适用于小图。面试中可能会问到Floyd的实现及其适用范围。

5. Prim算法和Kruskal算法

关联

• Prim和Kruskal都是最小生成树（MST）算法，通常用于无向图。
• 它们都是贪心算法，通过不同的方法来构造最小生成树。

区别

• Prim：逐步扩展生成树的节点，适合稠密图。
• Kruskal：通过选择最小的边逐步合并生成树，适合稀疏图。

关键点

• 时间复杂度：Prim为O(E log V)（堆优化），Kruskal为O(E log E)。
• 适用场景：网络设计、最小代价连接等。
• 优缺点：Prim对稠密图较好，Kruskal对稀疏图较好。面试中常问到如何实现Union-Find（用于Kruskal中的连通性检测）。

总结与面试中的关键考查点

1. 算法适用场景：每种算法都有特定的应用场景，面试中可能会考查候选人能否识别何时使用BFS、DFS、Dijkstra、Floyd或MST算法。
2. 算法的优化和复杂度：了解时间和空间复杂度，尤其是如何优化（如Dijkstra的优先队列优化，Kruskal的Union-Find等），可以帮助在面试中展示优化思维。
3. 差异点：
   • Dijkstra与Bellman-Ford的差异：特别在处理负权边的能力上。
   • Prim与Kruskal：适用图密度的不同，考查对图结构的理解。
   • 多源最短路径（Floyd）与单源最短路径（Dijkstra、Bellman-Ford）的区别，考查对路径搜索的理解。
4. 细节实现和边界情况：面试中可能会问到实现细节和一些边界情况，比如：
   • Dijkstra的贪心限制，无法处理负权边。
   • Bellman-Ford如何检测负权环。
   • Union-Find在Kruskal中的应用及优化。

Union-Find 并查集

Union-Find（联合-查找）是一种用于处理动态连通性问题的数据结构，通常用于图的连通性检测、最小生成树（如Kruskal算法中的使用）、网络连接问题等。

主要功能

Union-Find 数据结构主要提供两个操作：

1. Find（查找）：用于查找某个元素所在的集合（也可以理解为查找某个元素的代表元素或根节点）。
2. Union（合并）：将两个元素所属的集合合并成一个集合。

这两个操作支持高效的动态连接操作，适用于处理图的连通性问题。例如，判断图中两个节点是否在同一连通分量中，或合并两个节点所属的连通分量。

数据结构实现

Union-Find 使用一棵树来表示每个集合的结构。每个节点指向一个父节点，根节点代表整个集合。通过路径压缩和按秩合并（按大小合并）这两种技术，可以使操作的时间复杂度接近常数时间（$O(α(n))$，其中α是反阿克曼函数，是非常慢增长的）。

Find 操作

• 目标：查找一个元素属于哪个集合。即找到该元素的根节点。
• 路径压缩：为了优化后续查询，我们将路径中的所有节点都直接连接到根节点上，使得树更平衡，从而提高效率。

1
2
3
4
5
6
7
8
9

int find(int x)
{
    if (parent[x] != x)
    {
        parent[x] = find(parent[x]);
        // 递归查找并压缩路径
    }
    return parent[x];
}

Union操作

• 目标：将两个元素合并到同一个集合中。

• 按秩合并（Union by Rank/Size）：将树小的根节点连接到大的根节点，保持树的平衡，避免树变得过高。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

void union(int x, int y)
{
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY)
    {  // 如果 x 和 y 不在同一集合
        if (rank[rootX] > rank[rootY])
        {
            parent[rootY] = rootX;
        }
        else if(rank[rootX] < rank[rootY])
        {
            parent[rootX] = rootY;
        }
        else
        {    
            parent[rootY] = rootX;
            rank[rootX]++;
            // 增加秩
        }
    }
}

时间复杂度

• Find 和 Union 的时间复杂度是接近 O(α(n))，其中 α(n) 是反阿克曼函数，它增长非常慢，实际上几乎可以认为是常数时间（对于实际应用，α(n) 小于 5 即可）。
• 因此，Union-Find 数据结构非常高效，适用于处理大规模的连通性问题。

应用场景

1. 判断两个元素是否在同一个集合中：比如判断图中的两个节点是否连通。
2. 最小生成树：Kruskal 算法中用于判断两条边是否连接在同一个连通分量中，若是，则跳过；若不是，则合并两个分量。
3. 网络连接问题：如社交网络中的朋友关系，或者计算机网络中设备的连通性。
4. 动态连通性：例如实时地在网络中查询两个节点是否连通，并合并它们的连接。

例子

假设有一个图，节点为 0, 1, 2, 3，边为 (0,1), (1,2), (2,3)，我们可以用 Union-Find 来检测这些节点是否在同一个连通分量内，并且合并这些连通分量。

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
55
56
57

#include <iostream>
#include <vector>

class UnionFind {
private:
    std::vector<int> parent;
    std::vector<int> rank;

public:
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;  // 初始化每个元素的父节点为自身
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 路径压缩
        }
        return parent[x];
    }

    void unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
};

int main() {
    UnionFind uf(4);

    // 合并 (0, 1), (1, 2), (2, 3)
    uf.unionSets(0, 1);
    uf.unionSets(1, 2);
    uf.unionSets(2, 3);

    // 判断是否连通
    std::cout << "Is 0 and 3 connected? " << (uf.find(0) == uf.find(3)) << std::endl;  // 输出 1，表示连通
    std::cout << "Is 0 and 2 connected? " << (uf.find(0) == uf.find(2)) << std::endl;  // 输出 1，表示连通
    std::cout << "Is 0 and 4 connected? " << (uf.find(0) == uf.find(4)) << std::endl;  // 输出 0，表示不连通

    return 0;
}

关键特性

• 路径压缩：使得树更加扁平化，提高查询效率。
• 按秩合并：合并两个集合时，保持树的平衡，减少树的高度，进一步优化性能。

面试中可能的考点

1. Union-Find的基本原理，尤其是如何实现Find和Union操作。
2. 路径压缩和按秩合并的优化思路及其时间复杂度。
3. 在图算法中（特别是Kruskal算法）如何利用Union-Find来解决连通性问题。
4. 处理动态连通性时的常见问题，如如何动态添加边、合并不同的子图等。

总之，Union-Find 是一种非常高效的解决动态连通性问题的数据结构，是图论问题中不可或缺的工具之一，特别在处理大规模图的场景中表现尤为突出。

动态规划

高阶马尔科夫模型。

一个问题是否是动态规划，决定因素在于某一状态是否依赖于前面的一些状态，至少要依赖多于一种的状态才行。贪心算法其实也是动态规划的一种，可以转化为简单的动态规划。而动态规划与贪心的区别就在于动态规划的眼光比较长远，而贪心只顾及眼前的利益。

动态规划常能解决的有：01背包问题。

简单来说动态规划就是把难以解决的问题分割为很多结构相似的小问题。

Fibonacci

斐波那契数列。

1
2

1 1 2 3 5 8 13 21 34 55 89

递归法

1
2
3
4
5
6
7
8

int fibo(int n)
{
    if(n == 1 || n == 2)
    {
        return 1;
    }
    return fibo(n - 1) + fibo(n - 2);
}

测试

1
2
3
4
5

int main(void)
{
    int i = fibo(8);
    return 0;
}

迭代法

即循环，无需硬件栈，速度更快，状态不重复，但是需要依赖表格。

1
2
3
4
5
6
7
8
9
10

int fibo2(int n)
{
    int dp[50] = {0};
    dp[1] = 1;
    dp[2] = 1;
    for(int i = 3; i <= n; ++i)
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
}

背包

起始于一种状态：有一个包，小偷偷东西，有大有小，有贵有贱。那么小偷就要考虑如何在有限的容量下拿尽多价值的东西。

递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

int vals[] = {5, 9, 7, 11, 16, 13};
int weights[] = {9, 11, 6, 15, 18, 14};
int ks(int n, int cap)
{
    if(n == 0)
    {
        return cap >= weights[n] ? vals[n] : 0;
    }
    // 如果不选，则价值为：
    int no = ks(n - 1, cap);
    // 如果选择的价值：（先初始化为不选）
    int yes = no;
    if(cap >= weights[n])
    {
        yes = ks(n - 1, cap - weights[n]) + vals[n];
    }
    return no >= yes ? no : yes;
}

测试，结果应为45

1
2
3
4

int main()
{
    int i = ks(5, 50);
}

迭代法

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

int vals[] = {5, 9, 7, 11, 16, 13};
int weights[] = {9, 11, 6, 15, 18, 14};
int ks2(int n, int cap)
{
    // 6行 51列
    int res[6][51] = {0};
    // 初始化表格
    // i指的是背包目前的容量
    for(int i = 0; i <= 50; ++i)
    {
        if(i < weights[0])// weights[0]对应于 第0号物品的重量
        {
            res[0][i] = 0;
        }
        else
        {
            res[0][i] = vals[0];
        }
    }
    // 遍历计算每一个状态
    // 行 对应于n
    for(int i = 1; i <= n; ++i)
    {
        // 列 对应于cap
        for(int j = 0; j <= cap; ++j)
        {
            int no = res[i - 1][j];
            int yes = no;
            if(j >= weights[i])
            {
                yes = vals[i] + res[i - 1][j - weights[i]];
            }
            res[i][j] = no >= yes ? no : yes;
        }
    }
    return res[n][c];
}

测试，结果应为45

1
2
3
4

int main()
{
    int i = ks2(5, 50);
}

背包变型 - 凑数

1
2
3
4
5
6
7
8
9
10

nums[] = 5 8 1 3 9 2 4 7 6 -> 能不能凑出25
bool mk_sum(n, target_val)
不取：mk_sum(n - 1, target_val)           ->能不能从剩下的n-1个中凑出tar
取： mk_sum(n - 1, target_val - nums[n])  ->能不能从剩下的n-1中凑出tar-nums[n]
    
两个状态之间应该取OR（或）的关系，只要有一边可以达到，则就可以凑出25
    
终止条件：
    （1）n = 0，此时看target_get和第0个数是否相等。
    （2）或者target_val为0（全不选即可凑为0）

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int sums[] = {5, 8, 1, 3, 9, 2, 4, 7, 6};//9个数
int mk_sum(int n, int target_val)
{   
    // 终止条件
    if(target_val == 0)return 1; //true
    if(n == 0)return target_val == nums[0];
    int no = mk_sum(n - 1, target_val);
    int yes = no;
    if(target_val >= nums[n])
    {
        yes = mk_sum(n - 1, target_val - nums[n]);
    }
    return no || yes;
}

迭代法

1
2
3

n ∈ [0, 8]
target ∈ [0, 99] //其实target应该无上限才对，本例只看99以下的凑数情况
所以需要 9 × 100 的数组

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

int sums[] = {5, 8, 1, 3, 9, 2, 4, 7, 6};
int mk_sum2(int n, int target_val)
{
    char res[9][100] = {0};//因为表中的值只能有0、1，为了节省空间，用char
    for(int i = 0; i <= n; ++i)
    {
        res[i][0] = 1;// 第0列，代表target_val为0，此时为凑0，即全不选即可
    }
    // 以下for其实可以替换为一句话：res[0][nums[0]] = 1
    for(int j = 1; j <= target_val; ++j)
    {
        // 在第0个数时，为一个终止条件，看j正好与自身nums[0]相等时正好能凑
        res[0][j] = j == nums[0];
    }
    // 计算表格中每一个状态
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= target_val; ++j)
        {
            char no = res[i - 1][j];
            char yes = no;
            if(nums[i] <= j)
            {
                yes = res[i - 1][j - nums[i]];
            }
            res[i][j] = yes || no;
        }
    }
    return res[n][target_val];
}

测试，结果应为1

1
2
3
4

int main()
{
    char i = mk_sum2(8, 45);//从八个数中凑45
}

每次两边二选一最后总数最大

若干个小球排列成一排，每个小球上面写有一个整数。
玩家a和玩家b依次拿走小球，一名玩家一次只能拿一个球，规定玩家a先拿，玩家b后拿，但是每个玩家每次只能拿走最左或最右的球。
游戏结束时，每个玩家已经拿走的球上面的数字之和就是他得到的分数。
玩家a和玩家b都绝顶聪明，他们总会采用最优策略。
请返回最后获胜者的分数。

示例：
小球序列用一个整型数组 A 表示。
如：arr = [1,2,100,3]
开始时玩家A只能拿走1或3。如果玩家A拿走1，则排列变为[2,100,3]，接下来玩家B可以拿走2或3，然后继续轮到玩家A。如果开始时玩家A拿走3，则排列变为[1,2,100]，接下来玩家B可以拿走1或100，然后继续轮到玩家A。玩家A作为绝顶聪明的人不会先拿3，因为拿了3之后玩家B将拿走100。所以玩家A会先拿1，让排列变为[2,100,3]，接下来玩家B不管怎么选，100都会被玩家A拿走、玩家A会获胜，分数为101。所以返回101。
如：arr = [1,100,2]
开始时玩家A不管拿1还是2，玩家B作为绝顶聪明的人，都会把100拿走。玩家B会获胜，分数为100，所以返回100。

结构体

可以自定义一个结构体，最后返回这个结构体，从而可以分析两个记录值。

1
2
3
4
5

typedef struct _Score
{
    int current;
    int other;
}Score;

current代表当前人的总分数，other代表另一个人的总分数。
第一次选时，假设current是A，other是B。
则第二次选时（问题深度加1），current是B，other是A。
可以用king代表函数名，函数中有两个参数，left代表最左数的下标，right代表最右数的下标。
king(left, right)表示A先选，返回值current表示A在left到right之间，和B一起轮流选后的总分，other表示B的总分。
通过分析，可以清晰地知道，只有left和right两个通路，以此可以递推出两个迭代函数。

1
2
3
4
5
6
7

1 2 100 3

king(left, right) = ?

最后最高得分：
第1人（A）选择left:  king(left + 1, right)  -- 此时Current变为B
第1人（A）选择right: king(left, right - 1)  -- 此时Current变为B

递归法

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

#include<iostream>
typedef struct _Score
{
    int current;
    int other;
}Score;
int arr[] = { 1, 2, 100, 3 };

Score king_recur(int left, int right)
{
    Score score;
    if (left == right)
    {
        score.current = arr[left]; // left == right, 只有一个数
        score.other = 0;
        return score;
    }
    Score left_score  = king_recur(left + 1, right);
    Score right_score = king_recur(left, right - 1);
    // left_score.other + arr[left]   表示 上次选的人 选择左之后 的分数
    // left_score.other + arr[right]  表示 上次选的人 选择右之后 的分数
    // left_score.current             表示  这次要选的人        的分数
    // 如果 上次的人选 左边 之后 的 分数 减去 这次要选的人 的分数，
    // 比  上次的人选 右边 之后 的 分数 减去 这次要选的人 的分数大，则 上次的人（current）选左边：
    if (left_score.other + arr[left] - left_score.current >= right_score.other + arr[right] - right_score.current)
    {
        // 上次的other成为了这次的current，选了左边，因此current = other+arr[left]
        score.current = left_score.other + arr[left];
        // 上次的current成为了这次的other
        score.other   = left_score.current;
    }
    else // 否则，上次的人（current）就选右边。
    {
        score.current = right_score.other + arr[right];
        score.other   = right_score.current;
    }
    return score;
}
int main()
{
    Score score = king_recur(0, 3);
    std::cout << "A: " << score.current << ", B: " << score.other << std::endl;
}

测试：A: 101, B: 5

复杂度分析

每一次迭代有2个分支，因此递归法的时间复杂度为$O(2^n)$。

迭代法

终止条件是：left == right。这时只剩下一个球，只能选择这个球，此时值为这个球的数字。
因此，在迭代法中，就可以先以对角线斜行进行初始化。
还有一些可以轻松排除的：left不可能大于right，这些位置的值都无效，左下半角数值无意义。

接下来，我们再来分析left = 0, right = 1的情况：

1. 如果上一次的人选走了0号（1），那么king(0, 1) => current = 2, other = 1
2. 如果上一次的人选走了1号（2），那么king(0, 1) => current = 1, other = 2
3. 即每一个格子的值都依赖于左边的格或下边的格。
   1. 如果选了左边，则和下方格的other加和，作为当前current，与下方格的current对比，求差值=左other+下数字价值-左current
   2. 如果选了下边，则和左方格的other加和，作为当前current，与左方格的current对比，求差值=下other+左数字价值-下current
   3. 如果差值1大于差值2，则选左边；如果差值2大于差值1，则选右边。

这种需要依赖左1和下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
49
50
51
52
53
54
55
56

int arr[] = { 1, 2, 100, 3 };
Score scores[4][4];
Score king_interation(int left, int right)
{
    for (int i = left; i <= right; ++i)
    {
        scores[i][i].current = arr[i];
        scores[i][i].other   = 0;
    }
    std::cout << "Matrix:" << std::endl;
    for (int i = 0; i < 4; ++i)
    {
        for (int j = 0; j < 4; ++j)
        {
            std::cout << scores[i][j].current << "," << scores[i][j].other << " ";
        }
        std::cout << std::endl;
    }
    for (int j = left + 1; j <= right; )
    {
        int i;
        for (i = left; i <= right - (j - i); ++i, ++j)
        {
            // i小，j大
            // 选右边的情况 优于 选左边的情况
            if (scores[i][j - 1].other + arr[j] - scores[i][j - 1].current >= scores[i + 1][j].other + arr[i] - scores[i + 1][j].current)
            {
                // 左边的other（以前选的）+ 这次选的右边
                scores[i][j].current = scores[i][j - 1].other + arr[j];
                scores[i][j].other = scores[i][j - 1].current;
            }
            else// 选右边的情况 差于 选左边的情况
            {
                // 右边的other（以前选的）+ 这次选的左边
                scores[i][j].current = scores[i + 1][j].other + arr[i];
                scores[i][j].other = scores[i + 1][j].current;
            }
        }
        j = j - i + 1;
    }
    return scores[left][right];
}
int main()
{
    score = king_interation(0, 3);
    std::cout << "Matrix:" << std::endl;
    for (int i = 0; i < 4; ++i)
    {
        for (int j = 0; j < 4; ++j)
        {
            std::cout << scores[i][j].current << "," << scores[i][j].other << " ";
        }
        std::cout << std::endl;
    }
    std::cout << "A: " << score.current << ", B: " << score.other << std::endl;
}

优化逻辑

其实可以直接比较得分而无需计算差值。
我们之所以不使用“差值”进行比较，是因为这里的目标并不是仅仅最大化与对手的得分差，而是获得尽可能多的分数。在这个游戏的规则下：

• 每个回合的目标是为当前玩家（无论是A还是B）取得当前回合的最高得分；
• 同时，下一轮再以递归的方式计算对手得分的最大化策略。

因此，差值并不能准确反映最佳选择，因为差值只考虑到某一轮次的得失，而不是整个局面的最优解。而在动态规划中，我们将所有可能的得分组合记录下来，从而避免错过任何潜在的最优策略。

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

Score king_interation(int left, int right)
{
    for (int i = left; i <= right; ++i)
    {
        scores[i][i].current = arr[i];
        scores[i][i].other   = 0;
    }
    std::cout << "Matrix:" << std::endl;
    for (int i = 0; i < 4; ++i)
    {
        for (int j = 0; j < 4; ++j)
        {
            std::cout << scores[i][j].current << "," << scores[i][j].other << " ";
        }
        std::cout << std::endl;
    }
    for (int j = left + 1; j <= right; )
    {
        int i;
        for (i = left; i <= right - (j - i); ++i, ++j)
        {
            // 选择左边或右边球
            int pickLeft = arr[i] + scores[i + 1][j].other;
            int pickRight = arr[j] + scores[i][j - 1].other;
        
            // 选择更优策略
            if (pickLeft > pickRight) {
                scores[i][j].current = pickLeft;
                scores[i][j].other = scores[i + 1][j].current;
            }
            else {
                scores[i][j].current = pickRight;
                scores[i][j].other = scores[i][j - 1].current;
            }
        }
        j = j - i + 1;
    }
    return scores[left][right];
}

动态规划与贪心的区别

在这个动态规划的方案中：

1. 完整性：动态规划表记录了从每一个子问题的解开始，构建整个问题的解。这样就保证了即使在更早的步骤中没有获得“局部最高得分”，也能通过累计得到最终的最优解。
2. 非贪心性：如果采用贪心策略，每一步都会选择当前“最显眼”的得分选项（例如，选择最大值或最小值），忽视之后的可能得分。然而动态规划在 scores[i][j] 中记录了所有可能选项带来的得分情况，使得每一步都是基于整体最优，而非局部最优。对于 [0, 3] 的序列，不直接依赖于局部差值，而是递归地从 scores[0][1], scores[1][3] 等子问题的最优解构建整个区间的最优解。

总结

这道题的难点在于：current、other这两个变量名我们是固定好的，但是每一次选完之后，current和other的实际身份互换。要在错综复杂的分析中明确迭代方程在本层与上一层之间的联系、区别。同时，if条件表达式比较长，需要保持清楚的逻辑分析出，究竟需要看什么条件，此题不只是简单的看谁最终取得最大值，而是在过程中，看A选左边或右边之后，与B的差值，哪个大。

Playing with Beads

There are N people in a group labeled from 1 to N. People are connected to each other via threads in the following manner.
The person with label number K is connected to all the persons with label J such that J exactly divides K. Beads can be passed through the threads. If a person P has a bead, in how many ways can the bead be passed in the network of threads so that it returns to the same person within X moves or less?

MOVE: Passing the bead from one person to the other.

Input specification:
input1: N, denoting the number of people.
input2: P, label of the person having the bead
input3: X, maximum number of moves that can be made

Output specification:
Your function should return the total number of ways in which the bead will return to its initial position within X moves.

Example 1:

1
2
3
4
5
6
7
8
9

input1: 3
input2: 2
input3: 2

Output: 1

Explanation:
Only 1 way:
2->1->2

Example 2:

1
2
3
4
5
6
7
8
9
10
11

input1: 3
input2: 2
input3: 4

Output: 3

Explanation:
3 ways:
2->1->2
2->1->3->1->2
2->1->2->1->2

分析

假如K可以被J整除，则K和J相连。相连者可以互传球。

1. 输入1：共有N个人。标记为1到N。
2. 输入2：从P开始传球
3. 输入3：在X步内，有多少种方法可以传回同一人？

递归法

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

#include<iostream>
int n;
int begin;
int playbeads_recur(int p, int x)
{
    int sum = 0;
    if (x == 0)
    {
        std::cout << "End" << std::endl;
    }
    else
    {
        for (int i = 1; i <= n; ++i)
        {
            if ((i % p == 0 || p % i == 0) && (i != p))
            {
                std::cout << p << "->" << i << ", " << std::endl;
                if (i == begin)
                {
                    sum += 1;
                    std::cout << "This is a Way" << std::endl;
                }
                sum += playbeads_recur(i, x - 1);
            }
        }
    }
    return sum;
}
int main()
{
    n = 3;
    begin = 2;
    int x = 4;
    int sum = playbeads_recur(begin, x);

    std::cout << "Total Ways: " << sum << std::endl;
}

结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2->1,
1->2,
This is a Way
2->1,
1->2,
This is a Way
End
1->3,
End
1->3,
3->1,
1->2,
This is a Way
End
1->3,
End
Total Ways: 3

迭代法

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

#include<iostream>
int n;
int begin;
int arr[4][5];
int playbeads(int p, int x)
{
    for (int i = 0; i <= n; ++i)
    {
        for (int j = 0; j <= x; ++j)
        {
            arr[i][j] = 0;
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        if (begin == i)
        {
            arr[i][0] = 1;
        }
    }
    std::cout << "Matrix" << std::endl;

    for (int i = 0; i <= n; ++i)
    {
        for (int j = 0; j <= x; ++j)
        {
            std::cout << arr[i][j] << " ";
        }
        std::cout << std::endl;
    }
    // i 是 第几人
    // j 是 剩下几步
    for (int j = 1; j <= x; ++j)
    {
        for (int i = 1; i <= n; ++i)
        {
            // 注意，i==begin 且 j==x时表示第一步球在p手中，不能算
            if (i == begin && j != x)
            {
                arr[i][j] += 1;
            }
            for (int k = 1; k <= n; ++k)
            {
                if ((i != k) && (i % k == 0 || k % i == 0))
                {
                    arr[i][j] += arr[k][j-1];
                }
            }
        }
    }
    std::cout << "Matrix" << std::endl;
    for (int i = 0; i <= n; ++i)
    {
        for (int j = 0; j <= x; ++j)
        {
            std::cout << arr[i][j] << " ";
        }
        std::cout << std::endl;
    }
    return arr[p][x];
}
int main()
{
    n = 3;
    begin = 2;
    int x = 4;
    //int sum = playbeads_recur(begin, x);
    int sum = playbeads(begin, x);
    std::cout << "Total Ways: " << sum << std::endl;
}

输出：

1
2
3
4
5
6
7
8
9
10
11

Matrix
0 0 0 0 0
0 0 0 0 0
1 0 0 0 0
0 0 0 0 0
Matrix
0 0 0 0 0
0 1 1 3 3
1 1 2 2 3
0 0 1 1 3
Total Ways: 3