算法笔记note2

第二部分 后五章

第9章 树

9.1 树与二叉树

1.树的定义与性质

1. 可以没有结点,称为空树
2. 树的层次,从根节点开始算起
3. 度,树中节点最大的度称为树的度,就是节点的子树颗数
4. 边数为n-1
5. 深度,和层次差不多的意思
6. 森林,若干树的集合

2.二叉树的递归定义

两种特殊的二叉树:

1. 满二叉树:即每一层的节点都达到最大值
2. 完全二叉树:即除最后一层,其余层都达到最大值,且节点从左往右连续存在

对于参数中是否用引用的理解: 如果这个参数会被更改,则用引用,如链表初始化时传入一个头节点,如果是在init函数中初始化的话,不用引用就相当于简单的传值,传值被更改影响不到外面的头节点;如果这个只是修改这个参数的内容,可以不用引用, 不过有一说一引用,用就完事了,但还是要了解一下引用和不用的区别, 尽量使用引用,避免复制，效率更高

3.二叉树的存储结构和基本操作

存储结构:

//1.一般的二叉树
typedef struct node
{
    int data;
    node* l_child;
    node* r_child;
}*TREE;
//2.完全二叉树或满二叉树,由于其特殊性质,不难看出,对于第i个节点,它的左孩子是2i,右孩子是2i+1
//对此可以采用数组直接顺序存储,存储的顺序可以看作完全二叉树/满二叉树的层序遍历
//对于一般的二叉树也可以采用顺序存储,但对于空节点也需要存储,空间开销大

9.2 二叉树遍历

1.基本遍历

1.前序 中序 和 后序 遍历

这三个中算法基本一样,整体思路都是dfs不断向下递归,尤其是前序和后序,可以用来确定根节点,前序是第一个,后序是最后一个, 根中序结合起来,可以 用来确定左右子树,这也是后面根据前序/后序 序列 和 一个中序序列确定二叉树的思路

2.层序遍历

以bfs为思路,每次出队输出 并将 该节点的左右子节点入队

这里的一个关键算法,根据前序/后序/层序 序列 + 中序序列 构建二叉树

#include <iostream>
#include <queue>

int IN[30];    //保存中序序列
int POST[30];  //保存后序序列

class TREE
{
    public:
    struct node {
        int data;
        node *l_child;
        node *r_child;
    };
    using NODE = node *;

    TREE():root(nullptr){}

    void layer_display();

    void Creat(int lin,int rin,int lpost,int rpost)
    {
        root=creat(lin, rin, lpost, rpost);
    }

    NODE creat(int LIN, int RIN, int LPOST, int RPOST);

private:
    NODE root;
};



//IN   中序序列  [LIN,RIN]
//POST 后序序列  [LPOST,RPOST]

//整体思路 根据 中序序列 与 其他序列的特点来实现, 其他序列主要用来找到根节点,然后用中序序列划分为左右
//子树, 因为 我们知道 树是递归定义的 , 树的子结点又是一颗树, 就这样从根节点向下递归生成一颗完整的树

TREE::NODE TREE::creat(int LIN, int RIN, int LPOST, int RPOST)
{
    //递归边界 后序序列 长度小于等于0时
    if (LPOST > RPOST)
        return nullptr;

    //创建 当前 root 节点
    TREE::NODE root = new TREE::node;

    root->data = POST[RPOST];

    //找出中序序列中的root节点位置,方便后面讲中序序列 划分为左右子树
    int k;
    for (k = 0; k <= RIN;k++)
    {
        if (IN[k]==POST[RPOST])
            break;
    }

    //记录左子树中节点个数
    int num = k - LIN;

    //递归创建当前节点的左右子树
    root->l_child = creat(LIN, k - 1, LPOST, LPOST + num - 1);
    root->r_child = creat(k + 1, RIN, LPOST + num, RPOST - 1);
    return root;
}

//层序遍历 bfs 就从根节点开始 打印 判断左右子树是否为空,不为空入队 , 然后出队 ,再打印出队节点
//判断出队节点左右子树是否为空,不为空入队 , 循环直至 队列为空 
void TREE::layer_display()
{
    std::queue<TREE::NODE> my_queue;
    my_queue.push(root);

    while (!my_queue.empty())
    {
        TREE::NODE now = my_queue.front();
        my_queue.pop();

        if (now->l_child!= nullptr)
        {
            my_queue.push(now->l_child);
        }
        if (now->r_child!= nullptr)
        {
            my_queue.push(now->r_child);
        }
        if (!my_queue.empty())
            std::cout << now->data <<" ";
        else
            std::cout << now->data;
    }
}

int main()
{
    int n;
    std::cin >> n;

    for (int i = 0; i < n;i++)
        std::cin >> POST[i];
    for (int i = 0; i < n;i++)
        std::cin >> IN[i];

    TREE my_tree;
    my_tree.Creat(0, n - 1, 0, n - 1);
    my_tree.layer_display();

    return 0;
}

//一遍ac还是很爽的,感觉这块理解的应该还行,前序后序 应该都差不多,层序打算再写写看,大体上应该也差不多

2.二叉树的静态实现

用数组来表示罢了,可以尝试写一下,思路基本应该都是一样的

9.3 树的遍历

书中用的静态的,就是子节点用容器储存起来,如下是一个找权值的例题

#include <iostream>
#include <vector>
#include <algorithm>

const int MAXN = 200;

//对于一般树的解决,用容器容纳

struct node
{
    int weight;
    std::vector<int> child;
}NODE[MAXN];

bool cmp(int a,int b)
{
    return NODE[a].weight > NODE[b].weight;
}

// n = 节点数  m = 非叶节点数  s = 权值和
int n,m,s;

//path 记录路径 保存child
int path[MAXN];

//index 当前访问节点  numNode 当前path中的节点数  sum 权值和
void DFS(int index, int numNode, int sum)
{
    if (sum > s)
        return ;
    if (sum == s)
    {
        if (NODE[index].child.size() != 0)
            return ;

        for (int i=0; i<numNode; i++)
        {
            std::cout << NODE[path[i]].weight;

            if (i < numNode-1)
                std::cout << " ";
            else
                std::cout << std::endl;
        }
        return ;
    }

    for (int i=0;i<NODE[index].child.size();i++)
    {
        int child = NODE[index].child[i];
        path[numNode] = child;
        DFS(child,numNode+1,sum+NODE[child].weight);
    }
}

int main()
{
    int id,num,child;

    std::cin >> n >> m >> s;

    for (int i=0; i<n; i++)
        std::cin >> NODE[i].weight;

    for (int i=0; i<m; i++)
    {
        std::cin >> id >> num;

        for (int j=0;j<num;j++)
        {
            std::cin >> child;
            NODE[id].child.push_back(child);
        }
        //由于后面路径是按权值高低输出,在此处先对子节点按高到低排序
        std::sort(NODE[id].child.begin(),NODE[id].child.end(),cmp);
    }
    //第一个路径总是root
    path[0] = 0;
    DFS(0,1,NODE[0].weight);

    return 0;
}

9.4 二叉查找树

基本和普通二叉树一样,在创建时给了你条件,唯一注意的就是删除时的操作,找到当前删除节点的前继或后继,用前继或后继覆盖删除的节点,再将前继或后继节点删除即可,有个性质,二叉查找树的中序遍历是有序的

#include <iostream>
#include <queue>

struct node
{
    int data;
    node * l_child;
    node * r_child;
};

using NODE = node*;

void insert(NODE& root,int data)
{
    if (root == nullptr)
    {
        root = new node;
        root->data = data;
        root->l_child = nullptr;
        root->r_child = nullptr;
        return ;
    }
    else if (root->data == data)
        return;
    else if (data>root->data)
    {
        insert(root->r_child,data);
    }
    else
        insert(root->l_child,data);
}


NODE creat(int n)
{
    int data;
    NODE root = nullptr;
    for (int i=0;i<n;i++)
    {
        std::cin >> data;
        insert(root,data);
    }
    return root;
}

//用以找到前继或后继  ， 辅助删除函数
NODE find_max(NODE root)
{
    while (root->r_child != nullptr)
        root = root->r_child;
    return root;
}
NODE find_min(NODE root)
{
    while (root->l_child != nullptr)
        root= root->l_child;
    return root;
}

//删除
void deleteNode(NODE& root,int x)
{
    if (root == nullptr)
        return;
    if (root->data == x)
    {
        if (root->l_child == nullptr && root->r_child == nullptr)
        {
            root = nullptr;
        }else if (root->l_child != nullptr)
        {
            NODE pre = find_max(root->l_child);
            root->data = pre->data;
            deleteNode(root->l_child,pre->data);
        }else
        {
            NODE post = find_min(root->r_child);
            root->data = post->data;
            deleteNode(root->r_child,post->data);
        }
    }
    else if (root->data > x)
    {
        deleteNode(root->l_child,x);
    }
    else
        deleteNode(root->r_child,x);
}

//层序遍历
void layer_display(NODE& tree)
{
    std::queue<NODE> my_queue;
    my_queue.push(tree);

    while (!my_queue.empty())
    {
        NODE now = my_queue.front();
        my_queue.pop();
        std::cout << now->data << " ";
        if (now->l_child!= nullptr)
            my_queue.push(now->l_child);
        if (now->r_child!= nullptr)
            my_queue.push(now->r_child);
    }
    std::cout << std::endl;
}

void in_display(NODE& root)
{
    if (root!= nullptr)
    {
        in_display(root->l_child);
        std::cout << root->data <<" ";
        in_display(root->r_child);
    }
}

int main()
{
    int n;
    NODE tree;
    std::cin >> n;
    tree = creat(n);
    in_display(tree);
    std::cout << std::endl;
    deleteNode(tree,7);
    in_display(tree);
    return 0;
}

9.5 平衡二叉树

本质还是一个二叉查找树,但 我们知道有一种情况, 如果12345的顺序创建二叉查找树的话, 由于二叉查找树的性质, 比root大的创建到右子树, 这样的递增序列 会导致生成右斜树 ，查找效率和普通查找没区别, 平衡二叉树就是基于这个问题的改进, 会根据一定条件进行平衡 ， 不会出现上述情况

如何做到平衡: 平衡二叉树比起普通的二叉搜索树, 多了一个记录树的高度的变量，每次插入的时候计算平衡因子 (左右子树的高度只差不大于1) ， 如果大于1就会自动平衡

如何平衡: 插入时计算平衡因子, 根据平衡因子是 2 还是 -2 ，分为两种情况 LL ,LR 和 RR , RL 一共四种情况

上述是 LL LR 的情况,还是比较好理解的 ,下面是RR RL 的情况

汇总:

其中 需要用到的函数 计算树高 左旋函数 右旋函数 计算平衡因子 其他和普通二叉搜素树一样

//此种平衡树的建立 自下向上建立的 , 由插入的节点逐渐向上层计算 平衡因子 
//例子 5 4 2 8 6 9  应该形成如下的二叉树
//      6
//   4      8
// 2   5      9
#include <iostream>
#include <algorithm>
using namespace std;

struct node
{
    int data;
    int height;
    node *l_child;
    node *r_child;
};
using NODE = node*;

//获取树高
int get_height(NODE& root)
{
    if (root == nullptr)
        return 0;
    else
        return root->height;
}

//更新树高
void update_height(NODE& root)
{
    root->height = std::max(get_height(root->l_child), get_height(root->r_child))+1;
}

//计算平衡因子
int BF(NODE& root)
{
    return (get_height(root->l_child)- get_height(root->r_child));
}

//建立新节点
NODE newNode(int data)
{
    NODE root = new node;
    root->data = data;
    root->height = 1;
    root->l_child = root->r_child = nullptr;
    return root;
}

//左旋
void L(NODE& root)
{
    NODE temp = root->r_child;
    root->r_child = temp->l_child;
    temp->l_child = root;
    root = temp;
    update_height(root->l_child);
    update_height(root);
}
//右旋
void R(NODE& root)
{
    NODE temp = root->l_child;
    root->l_child = temp->r_child;
    temp->r_child = root;
    root = temp;
    update_height(root->r_child);
    update_height(root);
}

//插入
void insert(NODE& root, int data)
{
    if (root == nullptr)
    {
        root = newNode(data);
    }
    else if (root->data > data)
    {
        insert(root->l_child,data);
        update_height(root);
        if (BF(root) == 2)
        {
            if (BF(root->l_child) == 1)
            {
                R(root);
            }
            else
            {
                L(root->l_child);
                R(root);
            }
        }
    }
    else
    {
        insert(root->r_child,data);
        update_height(root);
        if (BF(root) == -2)
        {
            if (BF(root->r_child) == -1)
            {
                L(root);
            }
            else
            {
                R(root->r_child);
                L(root);
            }
        }
    }
}

NODE creat(int n)
{
    int data;
    NODE root = nullptr;

    for (int i=0; i<n; i++)
    {
        std::cin >> data;
        insert(root,data);
    }

    return root;
}

void post_display(NODE root)
{
    if (root)
    {
        post_display(root->l_child);
        post_display(root->r_child);
        std::cout << root->data << " ";
    }
}

int main()
{
    int n;
    NODE tree;
    n = 6;
    tree = creat(n);
    post_display(tree);
    return 0;
}

9.6 并查集

1.并查集的定义

维护集合数据结构,本质是一个数组,存储父结点,根结点指向自己

//对于上述集合
int fater[N];
father[1] = 1;
father[2] = 1;
father[3] = 2;
father[4] = 2;
father[5] = 5;
father[6] = 5;

2.并查集的基本操作

1. 初始化 : 每个元素都指向自己先
2. 查找 : 查找元素的根节点
3. 合并 : 将两个元素并入一个集合

上述操作直接看代码就完事了,比较好理解

3.路径压缩

看起来很难,实际上就是把一个集合内,除根节点外的元素,全部指向根节点,如以下集合

更改为如下集合

代码部分:

#include <iostream>

const int N = 10;
int father[N];
bool isRoot[N];

int find_father(int n)
{
    int a = n;
    while (n!=father[n])
        n = father[n];

        //路径压缩 n 为找到的根节点
        //在根据a节点 将路径上的所有节点全部指向根节点
    while (a!=father[a])
    {
        int z = a;
        a = father[a];
        father[z] = n;
    }
    return n;
}

void init(int n)
{
    for (int i = 1; i <= n;i++)
    {
        father[i] = i;
        isRoot[i] = false;
    }
}

void Union(int a,int b)
{
    int fa = find_father(a);
    int fb = find_father(b);

    if (fa!=fb)
        father[fa] = fb;
}

int main()
{
    int n, m;
    std::cin >> n >> m;
    int a, b;

    init(n);
    for (int i = 0; i < m;i++)
    {
        std::cin >> a >> b;
        Union(a, b);
    }

    int ans = 0;
    for (int i = 1; i <= n;i++)
        isRoot[find_father(i)] = true;

    for (int i = 1; i <= n;i++)
    {
        if (isRoot[i]==true)
            ans++;
    }
    std::cout << ans << std::endl;

    system("pause");
    return 0;
}

9.7 堆

1. 堆的定义与基本操作

首先是一棵完全二叉树,其次,根节点不小于或不大于孩子结点,不小于的称为大根堆,根节点永远是最大的,反之

#include <algorithm>

const int MAXN = 100;
int heap[MAXN] , n =10;

//low 为调整的元素 , high为最后一个元素
void downAdjust(int low,int high)
{
    //i为当前调整的元素,j为调整元素的左孩子
    int i=low,j=2*i;

    while (j <= high)
    {
        if (j+1 <= high && heap[j+1] > heap[j])
            j = j+1;

        if (heap[i] < heap[j])
        {
            std::swap(heap[i],heap[j]);
            i = j;
            j = 2*i;
        }
        else
            break;
    }
}

void creat(int n)
{
    //注意是倒着枚举,这样堆建成之时,就能满足大根堆的条件的了
    for (int i=n/2;i>=1;i--)
        downAdjust(i,n);
}

void delete_top()
{
    heap[1]= heap[n--];
    downAdjust(1,n);
}

//low是第一个结点 high是调整结点
void upAdjust(int low,int high)
{
    int i = high,j=i/2;
    while (j>=low)
    {
        if (heap[j]<heap[i])
        {
            std::swap(heap[j],heap[i]);
            i=j;
            j= i/2;
        }
        else
            break;
    }
}

void insert(int x)
{
    heap[++n] = x;
    upAdjust(1,n);
}

2.

9.8 哈夫曼树

主要就是构建思想,每次选最小的两个结点,合并,直到只剩最后一个结点

根据思想来比较简单,麻烦点就是再找出以及构建的集合中(多个树构成的集合,比如最开始就是五个根节点构成的集合),是根节点,且最小的两个下标,然后再合并成一棵树,加入集合

哈夫曼编码,由哈夫曼树得到的,对所有叶子结点遍历,若在左叶上就为1或0,右叶上就为0/1，取决你自己,最后得到的01串就是该叶子结点的哈夫曼编码

两种方式

1. 自底向上,用循环就能很容易的实现,思路就是当前结点的父节点不为 -1 时, 也就是当前节点只要有父节点就继续循环,并每次循环的时候判断为左子树还是右子树,加入 0 1 到字符串,最后将字符串反转,得到哈夫曼编码,
2. 自顶向下 能循环实现但毕竟麻烦,我是直接递归实现的,也就是dfs, 每次向下递归时，加入 0 1 到字符串,直到叶子节点就退出

//1.自底向上
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

struct node
{
    int w;
    int parent;
    int l_child;
    int r_child;
};
std::vector<node> tree;
std::vector<std::string> huffmancode(10);

void findMinTwo(int& min,int &max){
    int data = INT_MAX;
    int len = tree.size();
    for (int i=0;i<len;i++)
        if (tree[i].parent == -1 && tree[i].w < data){
            data = tree[i].w;
            min = i;
        }
    data = INT_MAX;
    tree[min].parent = -2;
    for (int i=0;i<len;i++)
        if (tree[i].parent == -1 && tree[i].w < data){
            data = tree[i].w;
            max = i;
        }
}

int main()
{
    int n,data;
    std::cin >> n;
    for (int i=1; i<=n; i++){
        std::cin >> data;
        tree.push_back({data,-1,-1,-1});
    }

    int z = n;
    for (int i=0;i<z-1;i++){
        int max,min;
        findMinTwo(min,max);
        tree[min].parent = tree[max].parent = n+i;
        tree.push_back({tree[min].w+tree[max].w,-1,min,max});
    }
    std::string temp;

    std::vector<std::string> huffman_code(n);
    for (int i=0;i<n;i++){
        node temp = tree[i];
        int pos = i;
        while (temp.parent != -1){
            node parent = tree[temp.parent];
            if (pos == parent.l_child)
                huffman_code[i] += '0';
            else
                huffman_code[i] += '1';
            pos = temp.parent;
            temp = parent;
        }
    }
    for (int i=0;i<n;i++){
        for (auto it = huffman_code[i].rbegin();it!=huffman_code[i].rend(); it++)
            std::cout << *it;
        std::cout << std::endl;
    }

    for (int i=0;i<n;i++)
        std::cout << huffmancode[i] << std::endl;
    return 0;
}

//2.自顶向下
#include <iostream>
#include <vector>
#include <string>

struct node
{
    char data;
    int weight;
    int parent;
    int l_child,r_child;
};

std::vector<node> tree;
std::vector<std::string> huffman_code(15);

void find_two_min(int& min1, int& min2)
{
    int weight = INT_MAX;
    int len = tree.size();
    for (int i=0;i<len;i++)
    {
        if (tree[i].parent == -1 && tree[i].weight < weight)
        {
            weight = tree[i].weight;
            min1 = i;
        }
    }
    weight = INT_MAX;
    tree[min1].parent = -2;
    for (int i=0;i<len;i++)
    {
        if (tree[i].parent == -1 && tree[i].weight < weight)
        {
            weight = tree[i].weight;
            min2 = i;
        }
    }
}

void DFS(int root, std::string temp)
{
    if (tree[root].l_child == -1 && tree[root].r_child == -1)
    {
        huffman_code[root] = temp;
        return ;
    }
    DFS(tree[root].l_child,temp+'0');
    DFS(tree[root].r_child,temp+'1');
}

int main()
{
    int n;
    while (std::cin >> n)
    {
        int weight;
        char data;
        for (int i=0;i<n;i++)
        {
            std::cin >> data >> weight;
            tree.push_back({data,weight,-1,-1,-1});
        }
        int z = n;
        for (int i=0;i<z-1;i++)
        {
            int min1,min2;
            find_two_min(min1,min2);
            tree[min1].parent = tree[min2].parent = n+i;
            tree.push_back({' ',tree[min1].weight+tree[min2].weight,-1,min1,min2});
        }
        DFS(2*n-2,"");
        for (int i=0;i<n;i++)
        {
            std::cout << tree[i].data << " " << huffman_code[i] << std::endl;
        }

        tree.clear();
        huffman_code.clear();
    }
    return 0;
}

目前想到的优化,更好的找two min 的函数，我的比较简单粗暴,就是一个个找，时间复杂度比较高

第10章图

10.1 图的定义和相关术语

G(V,E) G的顶点集V，边集E

顶点(vertex) 边(Edge)

入度:顶点的入边数量

出度:顶点的出边数量

有向图:边带方向的,此时入度不等于出度

无向图:边不带方向或者说是双向的,此时入度等于出度

权值:边上附带属性,如路径

10.2 图的存储

1.邻接矩阵

即用二维数组储存图,很直观,不过限制了内存,对于无向图的话,因为是对称矩阵,可以考虑压缩

2.邻接表

利用链表实现,减少不必要的内存开销,也可以用std::vector 实现

10.3 图的遍历

1.dfs

连通分量和强连通分量,差不多的东西，两顶点之间可以互相到达就是连通,无向图里为连通分量,有向图里为强连通分量

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <type_traits>

using MAX = std::integral_constant<int, 2010>::type;


int limit;                //阈值
int Person_Num = 0;       //图中顶点数量

bool vis[MAX::value] = {false};
std::map<std::string, int> StringToInt;//string 到 int 的映射
std::map<int, std::string> IntToString;//int 到 string 的映射
std::map<std::string,int> gang;

std::vector<std::vector<int>> matrix(MAX::value, std::vector<int>(MAX::value, 0));   //邻接矩阵
std::vector<int> weight(MAX::value,0);                                               //点权

void DFS(int now_visit, int& head, int& weight_total, int& area_member)
{
    vis[now_visit] = true;
    area_member++;

    if (weight[now_visit] > weight[head])
    {
        head = now_visit;
    }

    for (int i = 0; i < Person_Num;i++)
    {
        if (matrix[now_visit][i] > 0 )
        {
            weight_total += matrix[now_visit][i];
            matrix[now_visit][i] = matrix[i][now_visit] = 0;
            if (vis[i] == false)
            DFS(i, head, weight_total, area_member);
        }
    }
}

void DFS_Display()
{
    for (int i = 0; i < Person_Num;i++)
    {
        if (vis[i] == false)
        {
            int head = i, weight_total = 0, area_member = 0;
            DFS(i, head, weight_total, area_member);

            if (weight_total > limit && area_member > 2)
            {
                gang[IntToString[head]] = area_member;
            }
        }
    }
}

int change(std::string str)
{
    if (StringToInt.find(str) != StringToInt.end())
    {
        return StringToInt[str];
    }
    else
    {
        StringToInt[str] = Person_Num;
        IntToString[Person_Num] = str;
        return Person_Num++;
    }
}

int main()
{
    int n, w;
    std::string str1, str2;
    std::cin >> n >> limit;

    for (int i = 0; i < n;i++)
    {
        std::cin >> str1 >> str2 >> w;
        int id1 = change(str1);
        int id2 = change(str2);

        weight[id1] += w;
        weight[id2] += w;

        matrix[id1][id2] += w;
        matrix[id2][id1] += w;
    }

    DFS_Display();

    std::cout << gang.size() << std::endl;
    for (auto &it : gang)
    {
        std::cout << it.first << " " << it.second << std::endl;
    }

    return 0;
}

2.bfs

和之前第八章的基本一样

#include <iostream>
#include <vector>
#include <type_traits>
#include <queue>

using MAX = std::integral_constant<int, 10>::type;

int total, limit;

struct node
{
    int vertex;
    int layer;
    node (int v,int l):vertex(v),layer(l){}
};

std::vector<std::vector<node>> matrix(MAX::value);
bool IsEnqueue[MAX::value] = {false};

int BFS(int now_visit)
{
    int Num_Forward = 0;
    std::queue<node> q;
    node start(now_visit, 0);
    q.push(start);
    IsEnqueue[start.vertex] = true;

    while (!q.empty())
    {
        node now = q.front();
        q.pop();

        int vertex = now.vertex;

        for (int i = 0; i < matrix[vertex].size();i++)
        {
            node next = matrix[vertex][i];
            next.layer = now.layer + 1;

            //遍历要求 层数不大于上限 且未被访问 
            if (IsEnqueue[next.vertex] == false && next.layer <= limit)
            {
                //入队人数即是转发人数
                q.push(next);
                IsEnqueue[next.vertex] = true;
                Num_Forward++;
            }
        }
    }
    return Num_Forward;
}

int main()
{
    std::cin >> total >> limit;

    for (int i = 1; i <= total;i++)
    {
        int count;
        std::cin >> count;
        for (int j = 0; j < count;j++)
        {
            int data;
            std::cin >> data;
            matrix[data].push_back({i, 0});
        }
    }

    int count;
    std::cin >> count;
    for (int i = 0; i < count;i++)
    {
        int start;
        std::cin >> start;
        std::fill(IsEnqueue, IsEnqueue + MAX::value, false);
        std::cout << BFS(start) << std::endl;
    }

    system("pause");
    return 0;
}

10.4 最短路径

1.Dijkstra算法

单源最短路径,计算一个顶点到其他顶点的最短路径,思路比较简单,设定一个集合s,以及一个数组depth, depth用来记录起始点到其他点的距离,初始化状态起始点到其他所有点都为INT_MAX ,到自己为0，接下来就是不断查询起始点到其他顶点距离最短的,且没有被访问过的,每次将距离最短的加入集合s,也就是设置为以及访问过了,因为有了新的点的加入,更新depth数组

感觉像是贪心,每次都是当前最优解,最后整体最优解

时间复杂度O(n*n) ,邻接矩阵写法应该不好优化,因为内部有两个循环,邻接表写法可以优化查找过程,用堆来找最小的

#include <iostream>
#include <vector>
#include <type_traits>
#include <string>
#include <map>

int n = 6;

using LIMIT = std::integral_constant<int, 10000>::type;
using MAX = std::integral_constant<int, 6>::type;
std::vector<std::vector<int>> matrix(MAX::value, std::vector<int>(MAX::value, 0));

//记录路径
std::map<int,std::string> path;

bool IsVisit[6]{false};
int depth[6];

void MakeGraph()
{
    matrix[0][1] = 1;
    matrix[0][3] = 4;
    matrix[0][4] = 4;

    matrix[1][3] = 2;

    matrix[2][5] = 1;

    matrix[3][2] = 2;
    matrix[3][4] = 3;

    matrix[4][5] = 3;
    
}

void Dijkstra(int start)
{
    //初始化状态
    path[0]='0';
    std::fill(depth, depth + 6, LIMIT::value);
    depth[start] = 0;
    for (int i = 0; i < 6;i++)
    {
        //u   记录查询到的起始点到该顶点距离最小的点
        //min 用来方便查询
        int u = -1, min = LIMIT::value;
        for (int j = 0; j < n;j++)
        {
            if (depth[j] < min && IsVisit[j]==false)
            {
                u = j;
                min = depth[j];
            }
        }
        //若没找到说明没有连通了
        if (u == -1)
            return;
        IsVisit[u] = true;

        for (int v = 0; v < n;v++)
        {
            //更新depth状态 
            //条件: 1.没有被访问过 2.更新后更短 3.主要是看你图怎么设定的
            //比如我设定是0不连通,就需要加入>0,或者你设定为LIMIT::value也行
            if (IsVisit[v]==false && depth[u]+matrix[u][v]<depth[v] && matrix[u][v]>0)
            {
                depth[v] = depth[u] + matrix[u][v];
                path[v] = path[u] + (char)(v + '0');
            }
        }
    }
}

int main()
{
    MakeGraph();
    Dijkstra(0);

    system("pause");
    return 0;
}

另外一种情况存在多条最短路径时的处理

#include <iostream>
#include <vector>
#include <type_traits>

using LIMIT = std::integral_constant<int, 10000>::type;
using MAX = std::integral_constant<int, 5>::type;

std::vector<std::vector<int>> matrix(MAX::value, std::vector<int>(MAX::value, LIMIT::value));
std::vector<int> weight(MAX::value,0);
std::vector<bool> IsVisit(MAX::value,false);
std::vector<int> depth(MAX::value, LIMIT::value);
std::vector<int> w(MAX::value,0), num(MAX::value,0);
int start, end, vertex, edge;

void Dijkstra(int start)
{
    depth[start] = 0;
    w[start] = weight[start];
    num[start] = 1;

    for (int i = 0; i < vertex;i++)
    {
        int u = -1, min = LIMIT::value;
        for (int j = 0; j < vertex;j++)
        {
            if (IsVisit[j] == false && depth[j] < min)
            {
                min = depth[j];
                u = j;
            }
        }

        if (u == -1)
            return;

        IsVisit[u] = true;

        for (int v = 0; v < vertex;v++)
        {
            //有点疑问的就是为什么第一个if 里 num 直接覆盖 第二个是累加
            //思考 因为是贪心思想 逐步最优解 第一步的情况是最早发生的，此时depth[V]不确定,自然不能来到第二步
            //且最开始找到一条最短路径时,num也是不确定,第一个num[v]的值就是num[u]的值,后续再次找到的时候就累加上去
            //另外就是小于 为最优情况, 如果后续找到更短的路径, 直接将其覆盖
            if (IsVisit[v] == false && matrix[u][v] != LIMIT::value)
            {
                if (matrix[u][v] + depth[u] < depth[v])
                {
                    depth[v] = depth[u] + matrix[u][v];
                    w[v] = w[u] + weight[v];
                    num[v] = num[u];
                }
                else if (matrix[u][v]+depth[u] == depth[v])
                {
                    if (w[u]+weight[v] > w[v])
                    {
                        w[v] = w[u] + weight[v];
                    }
                    num[v] += num[u];
                }
            }
        }
    }
}

int main()
{
    std::cin >> vertex >> edge >> start >> end;
    for (int i = 0; i < vertex;i++)
    {
        std::cin >> weight[i];
    }

    for (int i = 0; i < edge;i++)
    {
        int a, b, c;
        std::cin >> a >> b >> c;
        matrix[a][b] = matrix[b][a] = c;
    }
    Dijkstra(start);
    std::cout << num[end] << " " <<  w[end] << std::endl;

    system("pause");
    return 0;
}

2.Bellman-ford算法 和 SPFA算法

1.Bellman-ford

用来处理边权有负数的情况,边权为负数时可能出现,负权环,此时求不出最短路径,因为只要你无限绕圈,最短路径就会无限小

关于这个算法的理解

//PATA 1003 重制版

#include <iostream>
#include <vector>
#include <type_traits>
#include <map>
#include <set>

using MAX = std::integral_constant<int, 5>::type;
using LIMIT = std::integral_constant<int, 10000>::type;

//first : vertxt , second : edge_weight
std::vector<std::vector<std::pair<int,int>>> matrix(MAX::value);
std::vector<int> weight(MAX::value);
std::vector<int> depth(MAX::value,LIMIT::value);
std::vector<int> num(MAX::value, 0);
std::vector<int> w(MAX::value, 0);
std::vector<std::set<int>> pre(MAX::value);

int vertex, edge, start, end;

bool BellmanFord(int start)
{
    depth[start] = 0;
    w[start] = weight[start];
    num[start] = 1;

    for (int i = 0; i < vertex - 1;i++)
    {
        int flag = 1;
        for (int j = 0; j < vertex;j++)
        {
            for (int v = 0; v < matrix[j].size();v++)
            {
                int id = matrix[j][v].first;
                int w1 = matrix[j][v].second;

                if (depth[j] + w1 < depth[id])
                {
                    depth[id] = depth[j] + w1;
                    w[id] = w[j] + weight[id];
                    flag = 0;
                    num[id] = num[j];
                    pre[id].clear();
                    pre[id].insert(j);
                }
                else if (depth[j]+w1 == depth[id])
                {
                    if (w[j] + weight[id] > w[id])
                    {
                        w[id] = w[j] + weight[id];
                    }
                    num[id] = 0;
                    pre[id].insert(j);
                    for (auto it : pre[id])
                    {
                        num[id] += num[it];
                    }
                }
            }
        }
        if (flag)
            break;
    }

    //判断负权环
    for (int j = 0; j < vertex;j++)
    {
        for (int v = 0; v < matrix[j].size();v++)
        {
            int id = matrix[j][v].first;
            int w1 = matrix[j][v].second;

            if (depth[j] + w1 < depth[id])
            {
                return false;
            }
        }
    }
    return true;
}

int main()
{
    std::cin >> vertex >> edge >> start >> end;

    for (int i = 0; i < vertex; i++)
    {
        std::cin >> weight[i];
    }

    for (int i = 0; i < edge; i++)
    {
        int a, b, c;
        std::cin >> a >> b >> c;
        matrix[a].push_back({b, c});
        matrix[b].push_back({a, c});
    }

    BellmanFord(start);

    std::cout << num[end] << " " << w[end] << std::endl;

    system("pause");
    return 0;
}
//flag 
//如果在某一次迭代中,depth没有发生改变,即已经找到最优解,直接退出循环

处理num(最短路径数量)时不用集合会出错,因为迭代的时候是对所有顶点的所有边处理,会发生重复处理的情况,std::set(集合pre)用来防止重复操作, std::set(集合pre)存储的是前缀，处理最大权和比较简单,因为就算重复处理了也仍然是最大权值，这也是和迪杰斯特拉的区别所在,迪杰斯特拉是一个点一个点处理,处理过的点已经找到最优,就不用在处理了,也就不会发生重复的情况,个人理解就是迪杰斯特拉是从个体到整体逐渐找到最优解,BellmanFord是从整体到局部逐渐最优, 由此如果限制步数的题目,就相当于对BellmanFord的迭代次数进行限制,看能不能找到最优解,而迪杰斯特拉无法直接处理,不过可以在找出来path的情况下,对path中的节点个数进行处理由此判断,关于为什么迭代次数最多是N-1次,个人理解:假设3个顶点,由一个点到另一个点的最长路径是n-1，也就是2次,所以在能找到解的最坏情况下,也就是n-1次,如果还要再走一步,成环的情况下就是回到自身了,而且这一步用来判断是否成负环

2.SPFA优化算法

由上面的可以发现,BellmanFord算法在迭代中存在大量重复操作,很显然能注意到的事情是,当一个顶点的depth发生改变时才会影响该顶点到其他节点的depth,所以只将改变的节点入队

//PATA1003
#include <iostream>
#include <vector>
#include <queue>
#include <type_traits>
#include <map>
#include <set>

using MAX = std::integral_constant<int, 5>::type;
using LIMIT = std::integral_constant<int, 10000>::type;

//first : vertex , second : edge_weight
std::vector<std::vector<std::pair<int, int>>> matrix(MAX::value);
std::vector<int> weight(MAX::value);
std::vector<int> depth(MAX::value, LIMIT::value);
std::vector<bool> IsEnqueue(MAX::value, false);
std::vector<int> w(MAX::value, 0);
std::vector<int> num(MAX::value,0);

int vertex, edge, start, end;

bool SPFA(int start)
{
    std::queue<int> q;
    depth[start] = 0;
    w[start] = weight[start];
    num[start] = 1;
    q.push(start);
    IsEnqueue[start] = true;

    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        IsEnqueue[start] = false;

        for (int v = 0; v < matrix[now].size();v++)
        {
            int id = matrix[now][v].first;
            int w1 = matrix[now][v].second;
            if (depth[now] + w1 < depth[id])
            {
                num[id] = num[now];
                w[id] = w[now] + weight[id];
                depth[id] = depth[now] + w1;
                q.push(id);
            }
            else if (depth[now] + w1 == depth[id])
            {
                if (w[now] + weight[id] > w[id])
                {
                    w[id] = w[now] + weight[id];
                }
                num[id] += num[now];
            }
        }
    }

    return true;
}

int main()
{
    std::cin >> vertex >> edge >> start >> end;

    for (int i = 0; i < vertex; i++)
    {
        std::cin >> weight[i];
    }

    for (int i = 0; i < edge; i++)
    {
        int a, b, c;
        std::cin >> a >> b >> c;
        matrix[a].push_back({b, c});
        matrix[b].push_back({a, c});
    }

    SPFA(start);
    std::cout << num[end] << " " << w[end] << std::endl;
    system("pause");
    return 0;
}

在BellmanFord熟悉的情况下,很容易,且不会重复访问,对于路径的确定也更清晰,原因在于只有在depth发生改变的时候才将该点加入迭代队列中,相等的时候直接处理就行了,这样就不会重复处理一个节点

还有点小疑点：num数组重复计算的问题，重复计算的具体实现，debug看一下什么时候出现重复

3.Floyd算法

难点在证明,算法结论很简单,不过三重循环O(n^3)的复杂度了,基本只能用于特定情况

结论:以一个中介点,不断迭代更新最短距离

#include <iostream>
#include <vector>
#include <type_traits>


//floyd
using MAX = std::integral_constant<int, 200>::type;
using LIMIT = std::integral_constant<int, 100000000>::type;

std::vector<std::vector<int>> matrix(MAX::value, std::vector<int>(MAX::value, LIMIT::value));

int n, m;

void Floyd()
{
    for (int k = 0; k < n;k++)
    {
        for (int i = 0; i < n;i++)
        {
            for (int j = 0; j < n;j++)
            {
                if (matrix[i][k] != LIMIT::value && matrix[k][j] != LIMIT::value
                 && matrix[i][k] + matrix[k][j] < matrix[i][j])
                 {
                     matrix[i][j] = matrix[i][k] + matrix[k][j];
                 }
            }
        }
    }
}

int main()
{
    int u, v, w;
    std::cin >> n >> m;
    for (int i = 0; i < n;i++)
    {
        matrix[i][i] = 0;
    }
    for (int i = 0; i < m;i++)
    {
        std::cin >> u >> v >> w;
        matrix[u][v] = w;
    }

    Floyd();

    for (int i = 0; i < n;i++)
    {
        for (int j= 0; j < n;j++)
        {
            if (matrix[i][j]!=LIMIT::value)
                std::cout << matrix[i][j] << "  ";
            else
            std::cout << "-1 ";
        }
        std::cout << std::endl;
    }
    system("pause");
    return 0;
}

10.5 最小生成树

1.prim算法

如果前一章认真看了的话,这个算法会很简单,基本和Dijkstra算法一样,唯一的区别在于dijkstra算法的depth数组计算的是每个点到源点的最短距离,prim计算的是每个点到集合的最短距离,思想也是一样,贪心逐步最优

#include <iostream>
#include <vector>
#include <type_traits>


//prim
using MAX = std::integral_constant<int, 6>::type;
using LIMIT = std::integral_constant<int, 10000>::type;

std::vector<std::vector<int>> matrix(MAX::value, std::vector<int>(MAX::value, LIMIT::value));
std::vector<bool> IsVisit(MAX::value, false);
std::vector<int> depth(MAX::value, LIMIT::value);

int vertex, edge;

int prim(int start)
{
    depth[start] = 0;
    int sum = 0;

    for (int i = 0; i < vertex;i++)
    {
        int u = -1, min = LIMIT::value;
        for (int j = 0; j < vertex; j++)
        {
            if (IsVisit[j]==false && depth[j] < min)
            {
                min = depth[j];
                u = j;
            }
        }
        if (u == -1)
            return sum;
        IsVisit[u] = true;
        sum += depth[u];

        for (int v = 0; v < vertex;v++)
        {
            if (matrix[u][v]!=LIMIT::value && IsVisit[v]==false && matrix[u][v] < depth[v])
            {
                depth[v] = matrix[u][v];
            }
        }
    }
    return sum;
}



int main()
{
    std::cin >> vertex >> edge;
    for (int i = 0; i < edge; i++)
    {
        int a, b, c;
        std::cin >> a >> b >> c;
        matrix[a][b] = matrix[b][a] = c;
    }
    std::cout << prim(0) << std::endl;
    system("pause");
    return 0;
}

2.kruskal算法

边贪心,思想比较简单,一开始将所有的顶点分为不同的连通块,对于所有的边,每次选取权值最小的,并将边的两顶点合并为一个连通块，直到选取的边数等于顶点数减一,如果不等于顶点数减一,说明没有连通所有顶点，实现就是枚举所有边,在枚举前已经看权值由大到小排好序了,对于是否在不同的连通块,以及合并到一个连通块,用并查集来实现,毕竟同一个端点就可以近似看成在同一个连通块，整体比较简单,但跟前面的实现有点区别，前面都是在图的基础上实现的,这个直接根据边权实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <type_traits>

//Kruskal
using MAX = std::integral_constant<int, 10>::type;
std::vector<int> father(MAX::value);

int Find_Father(int n)
{
    int a = n;
    while (n!=father[n])
    {
        n = father[n];
    }
    while (a!=father[a])
    {
        int z = a;
        a = father[a];
        father[z] = n;
    }
    return n;
}

struct node
{
    int u, v;
    int cost;
} edge[MAX::value];

bool cmp(node a,node b)
{
    return a.cost < b.cost;
}

int vertex, edge_num;

int Kruskal()
{
    int ans = 0, count = 0;
    for (int i = 0; i < father.size();i++)
    {
        father[i] = i;
    }
    std::sort(edge, edge + edge_num, cmp);

    for (int i = 0; i < edge_num;i++)
    {
        int fa = Find_Father(edge[i].u);
        int fb = Find_Father(edge[i].v);

        if (fa != fb)
        {
            father[fa] = fb;
            ans += edge[i].cost;
            count++;
        }
        if (count == vertex-1)
            break;
    }
    if (count != vertex-1)
    {
        return -1;
    }
    else
        return ans;
}

int main()
{
    std::cin >> vertex >> edge_num;
    for (int i = 0; i < edge_num;i++)
    {
        std::cin >> edge[i].u >> edge[i].v >> edge[i].cost;
    }
    std::cout << Kruskal() << std::endl;
    system("pause");
    return 0;
}

10.6 拓扑排序

1.有向无环图

如果一个有向图的任意顶点都无法通过一些有向边回到自身,那么称为有向无环图

2.拓扑排序

基于上面的有向无环图的概念,用来判断是否是有向无环图,以及这个拓扑序列

关于啥是拓扑序列:

graph TD;
    数学分析-->复变函数;
    数学分析-->常微分方程;
    数学分析-->计算方法;
    高等代数-->计算方法;
    空间解析几何-->复变函数;
    空间解析几何-->高等几何;
    复变函数-->实变函数;
    复变函数-->泛函分析;
    实变函数-->泛函分析;
    常微分方程-->高等几何;
    计算方法-->泛函分析;
    计算方法-->高等几何;

这样有前置课程逐步推向后续课程的序列即是拓扑序列,这是拓扑排序的用处之一,判断有向无环图也是他的用处

思路也很简单,将没有入度=0的结点加入队列,每次出队时,令与出队结点相邻的顶点的入度-1，如果为0了就入队,最后判断入队的结点数量是否等于顶点数,如果不等于说明不是有向无环图

补充:栈和队列都行,因为总之新节点想要入栈或入队,必须它的前置节点都已经入过队或栈了,栈和队列的不同实现,影响的只是同一层次节点在拓扑序列中的顺序

#include <iostream>
#include <type_traits>
#include <vector>
#include <queue>

using MAX = std::integral_constant<int, 4>::type;

std::vector<std::vector<int>> matrix(MAX::value);
std::vector<int> InDegree(MAX::value, 0);

int vertex, edge;

bool topologicalSort()
{
    int num = 0;
    std::queue<int> q;
    for (int i = 0; i < vertex;i++)
    {
        if (InDegree[i] == 0)
            q.push(i);
    }

    while (!q.empty())
    {
        int now = q.front();
        q.pop();

        for (int i = 0; i < (int)(matrix[now].size()); i++)
        {
            int id = matrix[now][i];
            InDegree[id]--;
            if (InDegree[id] == 0)
            {
                q.push(id);
            }
        }
        num++;
    }
    if (num==vertex)
        return true;
    else
        return false;
}

int main()
{
    std::cin >> vertex >> edge;

    for (int i = 0; i < edge; i++)
    {
        int a, b;
        std::cin >> a >> b;
        matrix[a].push_back(b);
        InDegree[b]++;
    }
    if (topologicalSort())
        std::cout << "YES" << std::endl;
    else
        std::cout << "NO" << std::endl;
    system("pause");
    return 0;
}

补充:拓扑排序是解决有向图中判环的算法,那么对于无向图中有哪些判环方法呢

1.并查集 和 Kruskal有点类似, 但不等于改为等于 , 如果两个顶点在合并前以及在同一集合中了, 说明存在环 ,

2.DFS 判断是否成环的两个条件 ， 当前访问结点到以及访问的结点存在边, 且该存在边的结点不是当前访问结点的父节点

3.BFS 也差不多吧,应该就是判断到已经入队节点是否存在边

10.7 关键路径

1.AOE网和AOV网

上学期看的时候, 没给全称, 全称 Activity on edge 和 Activity on vertex

一个描述边上的活动，一个描述点上的活动,上图的有向无环图就是AOV,aoe就是有边权的aov图

2.最长路径

直接边权乘以-1,照最短路径的求法求就行了,Dijkstra不行,无法处理负权图,用BellmanFord或SPFA就行了

3.关键路径

如何确定关键路径, 首先用e[r] 和 l[r] 表示活动ar的最早开始时间和最迟开始时间,很明显,如果e[r]=l[r]说明该活动为关键活动,问题在于如何求解

再设置一对数组 ve[i] 和 vl[i] 表示时间i的最早发生时间和最迟发生时间

graph LR
    事件vi-- 活动ar -->事件vj

利用这两个数组即可求解,e[r] 和 l[r]

1.e[r] = ve[i]

2.l[r] = vl[j] - length[r]

思路:主要为三步

1.利用拓扑排序求解ve数组 和 逆拓扑序列

2.利用逆拓扑序列求解vl数组

3.枚举所有顶点,根据ve数组和vl数组找出关键路径

有点注意点就是求解ve时是以大于为判断条件,求解vl时是以小于为判断条件

#include <iostream>
#include <queue>
#include <vector>
#include <type_traits>
#include <stack>
#include <map>

using MAX = std::integral_constant<int, 6>::type;

//first : vertex   second : edge
std::vector<std::vector<std::pair<int, int>>> matrix(MAX::value);
std::vector<int> InDegree(MAX::value, 0);
std::stack<int> TopSort;

std::vector<int> ve(MAX::value, 0), vl(MAX::value);

int vertex, edge;

bool topologicalSort()
{
    std::queue<int> q;
    for (int i = 0; i < vertex; i++)
    {
        if (InDegree[i] == 0)
        {
            q.push(i);
        }
    }
    
    //
    while (!q.empty())
    {
        auto now = q.front();
        q.pop();
        TopSort.push(now);

        for (int i = 0; i < matrix[now].size(); i++)
        {
            int id = matrix[now][i].first;
            int w = matrix[now][i].second;
            InDegree[id]--;
            if (InDegree[id] == 0)
            {
                q.push(id);
            }
            if (ve[now] + w > ve[id])
            {
                ve[id] = ve[now] + w;
            }
        }
    }

    if (TopSort.size() == vertex)
        return true;
    else
        return false;
}

int CriticalPath()
{
    if (topologicalSort() == false)
        return -1;
    else
        std::cout << "YES" << std::endl;

    std::fill(vl.begin(), vl.begin() + MAX::value, ve[vertex - 1]);
    while(!TopSort.empty())
    {
        auto now = TopSort.top();
        TopSort.pop();

        for (int i = 0; i < matrix[now].size(); i++)
        {
            int id = matrix[now][i].first;
            int w = matrix[now][i].second;
            if (vl[id]-w < vl[now])
            {
                vl[now] = vl[id] - w;
            }
        }
    }

    for (int i = 0; i < vertex; i++)
    {
        for (int v = 0; v < matrix[i].size();v++)
        {
            int id = matrix[i][v].first;
            int w = matrix[i][v].second;

            int e = ve[i], l = vl[id] - w;
            if (e == l)
            {
                std::cout << i << " " << id << std::endl;
            }
        }
    }
    return ve[vertex - 1];
}

int main()
{
    std::cin >> vertex >> edge;

    for (int i = 0; i < edge; i++)
    {
        int a, b, c;
        std::cin >> a >> b >> c;
        matrix[a].push_back({b, c});
        InDegree[b]++;
    }
    CriticalPath();
    system("pause");
    return 0;
}

第十一章 动态规划

11.1 动态规划的递归写法和地推写法

1.什么是动态规划

解决最优化问题的算法思想

2.动态规划的递归写法

#include <iostream>
#include <type_traits>

using MAX = std::integral_constant<int, 1000>::type;

int dp[MAX::value];

int Fibonacci(int n)
{
    if (n ==1 || n == 0)
        return 1;
    if (dp[n] != -1)
        return dp[n];
    else
    {
        dp[n] = Fibonacci(n - 1) + Fibonacci(n - 2);
        return dp[n];
    }
}

int main()
{
    std::fill(dp, dp + MAX::value, -1);
    std::cout << Fibonacci(5) << std::endl;
    return 0;
}

3.动态规划的递推写法

#include <iostream>
#include <type_traits>
#include <algorithm>

using MAX = std::integral_constant<int, 100>::type;

int matrix[MAX::value][MAX::value];
int dp[MAX::value][MAX::value];

int main()
{
    int n;
    std::cin >> n;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            std::cin >> matrix[i][j];
        }
    }
    for (int j = 1; j <= n; j++)
    {
        dp[n][j] = matrix[n][j];
    }

    for (int i = n-1; i >= 1;i--)
    {
        for (int j = 1; j <= i; j++)
        {
            dp[i][j] = std::max(dp[i + 1][j], dp[i + 1][j + 1]) + matrix[i][j]; //状态转移方程
        }
    }

    std::cout << dp[1][1] << std::endl;
    system("pause");
    return 0;
}

分治与动态规划的区别,分治处理的是不重叠的子问题,动态规划处理的是重叠子问题和最优子结构

11.2 最大连续子序列和