图解算法：五大常用算法

痛定思痛。 2022-11-07 04:09 243阅读 0赞

### 目录 ###

*  第一章 递归算法介绍
 *  第二章 递归算法应用
 *   *  2.1、求阶乘
     *  2.2、求年龄
 *  第三章 回溯算法介绍
 *  第四章 回溯算法应用
 *   *  4.1、走迷宫
     *  4.2、八皇后
 *  第五章 分治算法介绍
 *  第六章 分治算法应用
 *   *  6.1、汉诺塔
     *  6.2、棋盘覆盖
 *  第七章 动态规划介绍
 *  第八章 动态规划应用
 *   *  8.1、零一背包
     *  8.2、完全背包
 *  第九章 贪心算法介绍
 *  第十章 贪心算法应用
 *   *  10.1、分发饼干
     *  10.2、广播覆盖

--------------------

> 项目地址：https://gitee.com/caochenlei/algorithms

# 第一章 递归算法介绍 #

递归算法（recursion algorithm）又称递归法，简单的来说，就是函数自己调用自己。绝大多数编程语言中都支持函数的自调用，在这些语言中函数是可以通过调用自身来进行递归的。计算理论可以证明递归的作用可以完全取代循环，因此在很多函数编程语言中习惯用递归来实现循环。

那么“递归”和“循环”如何形象的描述呢？

*  **递归：** 你打开面前这扇门，看到屋里面还有一扇门。你走过去，发现手中的钥匙还可以打开他，你推开门，发现里面还有一扇门，你继续打开他。若干次之后，你打开面前的门后，发现只有一间屋子，没有门了。然后，你开始原路返回，最终还是可以返回到原点。一般来说，递归需要有边界条件（这里指最后那间屋子）、递归前进段（这里指去的过程）和递归返回段（这里指返回的过程）。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。
 *  **循环：** 在你打开门之前，手里就已经拿了若干把钥匙，每一把钥匙可以打开一道门，当你一扇一扇门打开过去，最终手里的钥匙就会全部用掉，最终成功的从房间里出去，也就是一去不复返，这里不考虑死循环。

# 第二章 递归算法应用 #

## 2.1、求阶乘 ##

计算阶乘的程序在数学上定义为：

![3771c63d1c85d013fc8c28e80a9a7135.png][]

而使用代码来实现却也是很简单：

public class Factorial { 
        public static void main(String[] args) { 
            System.out.println("5的阶乘：" + fact(5));
        }
    
        //求阶乘
        public static int fact(int n) { 
            if (n == 0) { 
                return 1;
            }
            return n * fact(n - 1);
        }
    }

5的阶乘：120

## 2.2、求年龄 ##

有5个人坐在一起，问第5个人多少岁，他说比第4个人大2岁。问第4个人多少岁，他说比第3个人大2岁。问第3个人多少岁，他说比第2个人大2岁。问第2个人多少岁，他说比第1个人大2岁。最后问第1个人，他说是10岁。请问第5个人多大？

计算年龄的程序在数学上定义为：

![035e9d23b7dc52c12086925e47901fb5.png][]

而使用代码来实现却也是很简单：

public class Age { 
        public static void main(String[] args) { 
            System.out.println(age(5));
        }
    
        //求年龄
        public static int age(int n) { 
            if (n == 1) { 
                return 10;
            }
            return age(n - 1) + 2;
        }
    }

# 第三章 回溯算法介绍 #

回溯算法（backtracking algorithm）又称试探法，实际上是一个类似枚举搜索尝试的过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。

我们实际上可以这么想，如果现在有一个迷宫，有一个入口，有一个出口，也只有一条路可以走出去，如果这个迷宫并没有规律，而是随机生成的，这个时候，一般来说，我们就会每一条路不停的尝试，发现这条路走不通，就会回退到某一点，然后继续尝试，直到最终走出去，其实这就是回溯的一种应用。

# 第四章 回溯算法应用 #

## 4.1、走迷宫 ##

![d79affc5047ec1e21c4a70e009ad2f76.png][]

首先我们需要创建一张地图，这里使用二维数组来代替地图中的数据，没有走过的路为0，红色墙的挡板为1，可以走的通路为2，走不通的路为3。上图的绿色方块和黄色方块并没有特殊意义，只是为了告诉大家迷宫入口和出口在哪里。当然了，地图可以设计的很复杂，里边的挡板也可以设计的很复杂，但是为了很好的让大家接受大家暂且和我保持一致，我们就使用上边那张地图。生成地图的代码如下：

public class Maze { 
        public static void main(String[] args) { 
            //1.创建地图
            int[][] map = createMap(10, 10);
    
            //2.打印地图
            System.out.println("初始化地图：");
            displayMap(map);
    
            //3.走迷宫
    
            //4.打印地图
    
        }
    
        //创建地图
        public static int[][] createMap(int rows, int cols) { 
            //...
        }
    
        //打印地图
    
        //走迷宫
    }

//创建地图
    public static int[][] createMap(int rows, int cols) { 
        //创建地图
        int[][] map = new int[rows][cols];
        //建立围墙
        for (int i = 0; i < rows; i++) { 
            for (int j = 0; j < cols; j++) { 
                //绘制第一行和最后一行的墙
                if (i == 0 || i == rows - 1) { 
                    map[i][j] = 1;
                }
                //绘制第一列和最后一列的墙
                if (j == 0 || j == cols - 1) { 
                    map[i][j] = 1;
                }
            }
        }
        //添加挡板
        map[4][0] = 1;
        map[4][1] = 1;
        map[4][2] = 1;
        map[4][3] = 1;
        map[5][6] = 1;
        map[5][7] = 1;
        map[5][8] = 1;
        map[5][9] = 1;
        //返回地图
        return map;
    }

生成完地图后，我们需要打印一下地图的数据来查看一下地图是否生成正确。打印地图的代码如下：

//打印地图
    public static void displayMap(int[][] map) { 
        //地图行数
        int rows = map.length;
        //地图列数
        int cols = map[0].length;
        //打印地图
        for (int i = 0; i < rows; i++) { 
            for (int j = 0; j < cols; j++) { 
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }

1 1 1 1 1 1 1 1 1 1 
    1 0 0 0 0 0 0 0 0 1 
    1 0 0 0 0 0 0 0 0 1 
    1 0 0 0 0 0 0 0 0 1 
    1 1 1 1 0 0 0 0 0 1 
    1 0 0 0 0 0 1 1 1 1 
    1 0 0 0 0 0 0 0 0 1 
    1 0 0 0 0 0 0 0 0 1 
    1 0 0 0 0 0 0 0 0 1 
    1 1 1 1 1 1 1 1 1 1

看着上边的地图，从绿色的入口出发，我们只能进行上下左右四个方向的走，因此，我们并不能确定先走哪一个方向比较好，并且上下左右有很多组合：

上 下 左 右 
    上 下 右 左 
    上 左 下 右 
    上 左 右 下 
    上 右 下 左 
    上 右 左 下 
    下 上 左 右 
    下 上 右 左 
    下 左 上 右 
    下 左 右 上 
    下 右 上 左 
    下 右 左 上 
    左 上 下 右 
    左 上 右 下 
    左 下 上 右 
    左 下 右 上 
    左 右 上 下 
    左 右 下 上 
    右 上 下 左 
    右 上 左 下 
    右 下 上 左 
    右 下 左 上 
    右 左 上 下 
    右 左 下 上

我们可以先观察地图，发现往右走和往下走比较好，所以，我们先指定一个走迷宫的策略：`下->右->上->左`，先往下走，往下走不通，往右走，往右走不通，往上走，往上走不通，往左走，我们就把这个点标记为3，直到我们走到迷宫的终点也就是黄色的方块处就可以了。

public class Maze { 
        public static void main(String[] args) { 
            //1.创建地图
            int[][] map = createMap(10, 10);
    
            //2.打印地图
            System.out.println("初始化地图：");
            displayMap(map);
    
            //3.走迷宫
            walkMap(map, 1, 1);
    
            //4.打印地图
            System.out.println("走迷宫打印：");
            displayMap(map);
        }
    
        //创建地图
        //代码省略
    
        //打印地图
        //代码省略
    
        /** * 走迷宫 * * @param map 要走的地图 * @param x 起始位置x坐标 * @param y 起始位置y坐标 * @return */
        public static boolean walkMap(int[][] map, int x, int y) { 
            //如果走出迷宫，则返回true
            if (map[8][8] == 2) { 
                return true;
            }
            //如果没有走出，则继续走迷宫
            if (map[x][y] == 0) { 
                //假定该点可以走
                map[x][y] = 2;
                //按照策略继续走
                if (walkMap(map, x + 1, y)) {            //往下走
                    return true;
                } else if (walkMap(map, x, y + 1)) {     //往右走
                    return true;
                } else if (walkMap(map, x - 1, y)) {     //往上走
                    return true;
                } else if (walkMap(map, x, y - 1)) {     //往左走
                    return true;
                } else {                                 //走不通
                    map[x][y] = 3;
                    return false;
                }
            }
            //如果这个方块不能再走（如：1遇墙、2已走过、3走不通）
            else { 
                return false;
            }
        }
    }

初始化地图：
    1 1 1 1 1 1 1 1 1 1 
    1 0 0 0 0 0 0 0 0 1 
    1 0 0 0 0 0 0 0 0 1 
    1 0 0 0 0 0 0 0 0 1 
    1 1 1 1 0 0 0 0 0 1 
    1 0 0 0 0 0 1 1 1 1 
    1 0 0 0 0 0 0 0 0 1 
    1 0 0 0 0 0 0 0 0 1 
    1 0 0 0 0 0 0 0 0 1 
    1 1 1 1 1 1 1 1 1 1 
    走迷宫打印：
    1 1 1 1 1 1 1 1 1 1 
    1 2 0 0 0 0 0 0 0 1 
    1 2 0 0 0 0 0 0 0 1 
    1 2 2 2 2 0 0 0 0 1 
    1 1 1 1 2 0 0 0 0 1 
    1 0 0 0 2 0 1 1 1 1 
    1 0 0 0 2 0 0 0 0 1 
    1 0 0 0 2 0 0 0 0 1 
    1 0 0 0 2 2 2 2 2 1 
    1 1 1 1 1 1 1 1 1 1

我们发现程序已经找到了出去迷宫的路了，那一条全是2的路就是赶往出口的路，当然了，你选择的行走策略不一样这个结果也有可能会不一样，我们目前选择的是`下->右->上->左`，而如果你想要找到路径最小的一条，那就需要把上边所有的行走策略全部走一遍，才能找到最小的一条，这里就不演示了。

## 4.2、八皇后 ##

八皇后问题（Eight queens），是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出的问题，是回溯算法的典型案例。

问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转，和对角线对称变换的摆法看成一类，共有42类。计算机发明后，有多种计算机语言可以编程解决此问题。

![04006cdda0c21c100a4fed4a8c16ad19.png][]

解决八皇后的具体思路：

1.  第一个皇后先放第一行第一列。
2.  第二个皇后放在第二行第一列、然后判断是否 OK， 如果不 OK，继续放在第二列、第三列、依次把所有列都放完，找到一个合适。
3.  继续第三个皇后，还是第一列、第二列……直到第 8 个皇后也能放在一个不冲突的位置，算是找到了一个正确解，然后输出当前8个皇后的位置。
4.  当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解， 全部得到。
5.  然后回头继续第一个皇后放第二列，后面继续循环执行 1,2,3,4 的步骤，直到找到所有的解。

在这个过程中，如何判断是否在同一行、同一列比较容易判断，但是如何判断在同一斜线是一个麻烦的问题，假设一个点A的坐标是\[ a , b \]，那么和该点在同一斜线上的点A有四种分别是：

![6c4b938d6a1e35309efd7086f6e1dbad.png][]

前两种点横纵坐标相减和A点横纵坐标相减后一样，后两种点横纵坐标相加和A点横纵坐标相加一样。

![203227f275814b3a14cadb9142b3eb9a.png][]

因此，根据这个我们就可以很方便的判断两个点是否在同一斜线上，只要两个点横纵坐标相加结果相等或者相减结果相等，就可以判断两个点在同一斜线上。

public class EightQueens { 
        private static int max = 8;                 //代表8个皇后的数量
        private static int[] arr = new int[8];      //代表8个皇后的下标
    
        public static void main(String[] args) { 
            check(0);
        }
    
        //开始摆放八个皇后
        public static void check(int n) { 
            //如果n=8则表明8个皇后已经放好，放好了就直接输出数组信息
            if (n == max) { 
                print();
                return;
            }
            //从当前行的第一列(0)开始逐一放八皇后并判断该皇后是否合法
            for (int i = 0; i < max; i++) { 
                //把当前列下标放到对应皇后的下标
                arr[n] = i;
                //下标是放好了但是合不合法需判断
                if (judge(n)) { 
                    check(n + 1);
                }
            }
        }
    
        //判断位置是否合法
        public static boolean judge(int n) { 
            //i代表皇后下标
            for (int i = 0; i < n; i++) { 
                //array[n] == array[i]代表：第n个皇后和第i个皇后是否在同一列
                //这里不用判断是不是在同一行，因为完全没有必要，8个皇后分别在8行上
                //Math.abs(n - i) == Math.abs(array[n] - array[i])代表：第n个皇后和第i个皇后是否在同一斜线
                if (arr[n] == arr[i] || Math.abs(n - i) == Math.abs(arr[n] - arr[i])) { 
                    return false;
                }
            }
            return true;
        }
    
        //输出8个皇后的位置
        public static void print() { 
            for (int i = 0; i < arr.length; i++) { 
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
    }

0 4 7 5 2 6 1 3 
    0 5 7 2 6 3 1 4 
    0 6 3 5 7 1 4 2 
    0 6 4 7 1 3 5 2 
    1 3 5 7 2 0 6 4 
    1 4 6 0 2 7 5 3 
    1 4 6 3 0 7 5 2 
    1 5 0 6 3 7 2 4 
    1 5 7 2 0 3 6 4 
    1 6 2 5 7 4 0 3 
    1 6 4 7 0 3 5 2 
    1 7 5 0 2 4 6 3 
    2 0 6 4 7 1 3 5 
    2 4 1 7 0 6 3 5 
    2 4 1 7 5 3 6 0 
    2 4 6 0 3 1 7 5 
    2 4 7 3 0 6 1 5 
    2 5 1 4 7 0 6 3 
    2 5 1 6 0 3 7 4 
    2 5 1 6 4 0 7 3 
    2 5 3 0 7 4 6 1 
    2 5 3 1 7 4 6 0 
    2 5 7 0 3 6 4 1 
    2 5 7 0 4 6 1 3 
    2 5 7 1 3 0 6 4 
    2 6 1 7 4 0 3 5 
    2 6 1 7 5 3 0 4 
    2 7 3 6 0 5 1 4 
    3 0 4 7 1 6 2 5 
    3 0 4 7 5 2 6 1 
    3 1 4 7 5 0 2 6 
    3 1 6 2 5 7 0 4 
    3 1 6 2 5 7 4 0 
    3 1 6 4 0 7 5 2 
    3 1 7 4 6 0 2 5 
    3 1 7 5 0 2 4 6 
    3 5 0 4 1 7 2 6 
    3 5 7 1 6 0 2 4 
    3 5 7 2 0 6 4 1 
    3 6 0 7 4 1 5 2 
    3 6 2 7 1 4 0 5 
    3 6 4 1 5 0 2 7 
    3 6 4 2 0 5 7 1 
    3 7 0 2 5 1 6 4 
    3 7 0 4 6 1 5 2 
    3 7 4 2 0 6 1 5 
    4 0 3 5 7 1 6 2 
    4 0 7 3 1 6 2 5 
    4 0 7 5 2 6 1 3 
    4 1 3 5 7 2 0 6 
    4 1 3 6 2 7 5 0 
    4 1 5 0 6 3 7 2 
    4 1 7 0 3 6 2 5 
    4 2 0 5 7 1 3 6 
    4 2 0 6 1 7 5 3 
    4 2 7 3 6 0 5 1 
    4 6 0 2 7 5 3 1 
    4 6 0 3 1 7 5 2 
    4 6 1 3 7 0 2 5 
    4 6 1 5 2 0 3 7 
    4 6 1 5 2 0 7 3 
    4 6 3 0 2 7 5 1 
    4 7 3 0 2 5 1 6 
    4 7 3 0 6 1 5 2 
    5 0 4 1 7 2 6 3 
    5 1 6 0 2 4 7 3 
    5 1 6 0 3 7 4 2 
    5 2 0 6 4 7 1 3 
    5 2 0 7 3 1 6 4 
    5 2 0 7 4 1 3 6 
    5 2 4 6 0 3 1 7 
    5 2 4 7 0 3 1 6 
    5 2 6 1 3 7 0 4 
    5 2 6 1 7 4 0 3 
    5 2 6 3 0 7 1 4 
    5 3 0 4 7 1 6 2 
    5 3 1 7 4 6 0 2 
    5 3 6 0 2 4 1 7 
    5 3 6 0 7 1 4 2 
    5 7 1 3 0 6 4 2 
    6 0 2 7 5 3 1 4 
    6 1 3 0 7 4 2 5 
    6 1 5 2 0 3 7 4 
    6 2 0 5 7 4 1 3 
    6 2 7 1 4 0 5 3 
    6 3 1 4 7 0 2 5 
    6 3 1 7 5 0 2 4 
    6 4 2 0 5 7 1 3 
    7 1 3 0 6 4 2 5 
    7 1 4 2 0 6 3 5 
    7 2 0 5 1 4 6 3 
    7 3 0 2 5 1 6 4

# 第五章 分治算法介绍 #

分治算法（divide and conquer algorithm）又称分治法，他的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分解目标完成程序算法，简单问题可用二分法完成。利用分治策略求解时，所需时间取决于分解后子问题的个数、子问题的规模大小等因素，而二分法，由于其划分的简单和均匀的特点，是经常采用的一种有效的方法，例如二分法检索。

当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。对于这类问题，我们往往先把他分解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把他们组合成求整个问题的解法。如果这些子问题还较大，难以解决，可以再把他们分成几个更小的子问题，以此类推，直至可以直接求出解为止，这就是分治策略的基本思想。

# 第六章 分治算法应用 #

## 6.1、汉诺塔 ##

法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔（Tower of Hanoi），又称河内塔。

![6e02171824eb5f59753604fea911fada.png][]

不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

不管这个传说的可信度有多大，如果考虑一下把64片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序，这需要多少次移动呢？假设有n片，移动次数是f(n)，显然f(1)=1，f(2)=3，f(3)=7，且f(k+1)=2\*f(k)+1。此后不难证明f(n)=2^n-1。n=64时，需要移动18446744073709551615次。假如每秒钟一次，那就是18446744073709551615秒。这表明移完这些金片需要5845.42亿年以上，而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。真的过了5845.42亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。

当n=1时，我们直接把这个金片由A柱移动到C柱即可。

当n=2时，我们首先把最小的金片由A柱移动到B柱，然后把A柱的金片移动到C柱，最后把B柱最小的金片移动到C柱。

![ac6f6bb3e870da9d85439474a54f4b1e.png][]

![bdf6976cca628cc345719dc64c47b435.png][]

![ce467b2fab1d4b0a9e3f664c46a97157.png][]

![cb050b21e080e5b3d180216eaae7acab.png][]

当n=3时，这时候步骤比较多，我就直接贴出移动步骤图了。

![4e63c98cb4eda11b3a3458fa8282cac5.png][]

![c4b34f9d62b2b4818673016c19675f91.png][]

![f26a3642ea9799a6b3c449e8eba8b307.png][]

![762451ef9e4f95e61a3555219db85216.png][]

![462e0ede3b54626cc9f4b769231e6139.png][]

![67aceddde4e56fc82c4881ba2e10aabf.png][]

![6ee4f107d198f188152353fcacf07af2.png][]

![4a4fa717f89d4b4df51856d74cf69116.png][]

当n=k时，这时候我们会发现移动盘子的步骤越来越复杂，我们可以把这一个问题进行拆分，当n=1和当n=2时，几步就搞定了，要是把这么复杂的问题抽成n=1时，直接把金片由A柱移动到C柱即可，当n=2时，一共三步的事情，那我们有没有一种可能，当n大于或者等于2的时候，我们把一堆金片分成两部分，最顶上的最小的那一片是一部分，其余剩下的是另外一部分。把第二部分看成一个整体来进行移动，具体细节不用管，因为我们会递归调用，计算机会帮我们逐渐将问题进行分解，最后分解成两部分的情况，然后我们就按照n=2这种情况来进行处理。

![cdb944a8acaac03d7f411159b99a7632.png][]

![7d331074d6fe175a1d4db64ddef59aae.png][]

![407e871b61d0423c5d754fc882cfd8de.png][]

![e0e8b42548b7a426ba6fa3639247d67d.png][]

上边讲解了很多，但是真正实现的代码却并不多，比较容易实现，代码如下：

public class Hanoi { 
        public static void main(String[] args) { 
            int n = 3;//我们这里金片假设为3片
            hanoi(n, 'A', 'B', 'C');
        }
    
        public static void move(char from, char to) { 
            System.out.printf("%c to %c\n", from, to);
        }
    
        public static void hanoi(int n, char a, char b, char c) { 
            //当只剩下一个金片的时候直接从A柱移动到C柱
            if (n == 1) { 
                move(a, c);
            }
            //当n>=2时就拆成两部分（n-1）代表第二部分
            else { 
                //将第二部分由A柱移动到B柱
                hanoi(n - 1, a, c, b);
                //将第一部分由A柱移动到C柱
                move(a, c);
                //将第二部分由B柱移动到C柱
                hanoi(n - 1, b, a, c);
            }
        }
    }

A to C
    A to B
    C to B
    A to C
    B to A
    B to C
    A to C

## 6.2、棋盘覆盖 ##

在一个2k×2k （k≥0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格。显然，特殊方格在棋盘中可能出现的位置有4k种，因而有4k种不同的棋盘，以下是几种情况的图示。棋盘覆盖问题要求用4种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。

![0ef16e3b91f624f76e50aacf6ef89b74.png][]

首先我们通过观察这些棋盘会发现这是一个四四方方的正方形，并且边长是2的倍数，我们可以通过这一点进行入手，当k非常大的时候，我们自己可能用手写不出来，但是，当k=1时，也就是一个2×2的棋盘，正好可以使用4种L型骨牌中的一种刚好把棋盘覆盖，我们是不是可以这么想，无论你的棋盘有多大，通过不停的二分法，将一个大的棋盘拆分成无数个2×2的棋盘，也就是分而治之，这完全符合分治算法的理念。

![4c83c05c958c274b24f11b6654319b80.png][]

当k=2时，我们再来分析一下，在棋盘里只有一块特殊的方格，而且棋盘的大小也比较特殊，2的K次方，非常适合切分成一半。又因为棋盘是个方形的，所以思路可以使将棋盘分成大小相同的四份。当我们将有特殊方格的棋盘分割成4个相同的子棋盘时，4个棋盘分成两类：有特殊方格和没有特殊方格。我们用到的L型骨牌刚好是三个方格的，也就是说可以用一个L型骨牌将其余的三个没有特殊方格的棋盘变成有特殊方格的。

![735447c165aec945ccaddb489660637c.png][]

在进行算法设计的时候，我们首先要明白，这个特殊的方格（红色），在一个棋盘中可能出现的位置有4k种，所以，我们必须自己指定这个特殊方格所在的位置，只要是在这个棋盘中，这个特殊方格都可以存放到任何位置，这里我们使用变量`dr`代表特殊方格横坐标，变量`dc`代表特殊方格纵坐标。

public class CheckerBoard { 
        private static int num = 0;                      //用于存放L型骨牌编号
        private static int[][] arr = new int[100][100];  //用于存放棋盘数组信息
    
        public static void main(String[] args) { 
            //设置棋盘大小
            int k = 2;
            int size = (int) Math.pow(2.0, k);
    
            //开始棋牌覆盖
            checkerBoard(0, 0, size - 1, size - 1, size);
    
            //打印二维数组
            for (int i = 0; i < size; i++) { 
                for (int j = 0; j < size; j++) { 
                    System.out.print(arr[i][j] + " ");
                }
                System.out.println();
            }
        }
    
        /** * 棋盘覆盖 * * @param tr 当前棋盘左上角的行号 * @param tc 当前棋盘左上角的列号 * @param dr 特殊方格所在的行号 * @param dc 特殊方格所在的列号 * @param size 当前棋盘的大小2^k */
        public static void checkerBoard(int tr, int tc, int dr, int dc, int size) { 
            int s, t;               //临时变量
            if (size == 1) return;  //临界条件
            s = size / 2;           //分割棋盘
            t = ++num;              //骨牌编号
    
            //覆盖左上角子棋盘
            if (dr < tr + s && dc < tc + s) { 
                //特殊方格在此棋盘中
                checkerBoard(tr, tc, dr, dc, s);
            } else { 
                //此棋盘中无特殊方格，用t号L型骨牌覆盖右下角
                arr[tr + s - 1][tc + s - 1] = t;
                //覆盖其余方格
                checkerBoard(tr, tc, tr + s - 1, tc + s - 1, s);
            }
    
            //覆盖右上角子棋盘
            if (dr < tr + s && dc >= tc + s) { 
                //特殊方格在此棋盘中
                checkerBoard(tr, tc + s, dr, dc, s);
            } else { 
                //此棋盘中无特殊方格，用t号L型骨牌覆盖左下角
                arr[tr + s - 1][tc + s] = t;
                //覆盖其余方格
                checkerBoard(tr, tc + s, tr + s - 1, tc + s, s);
            }
    
            //覆盖左下角子棋盘
            if (dr >= tr + s && dc < tc + s) { 
                //特殊方格在此棋盘中
                checkerBoard(tr + s, tc, dr, dc, s);
            } else { 
                //此棋盘中无特殊方格，用t号L型骨牌覆盖右上角
                arr[tr + s][tc + s - 1] = t;
                //覆盖其余方格
                checkerBoard(tr + s, tc, tr + s, tc + s - 1, s);
            }
    
            //覆盖右下角子棋盘
            if (dr >= tr + s && dc >= tc + s) { 
                //特殊方格在此棋盘中
                checkerBoard(tr + s, tc + s, dr, dc, s);
            } else { 
                //此棋盘中无特殊方格，用t号L型骨牌覆盖左上角
                arr[tr + s][tc + s] = t;
                //覆盖其余方格
                checkerBoard(tr + s, tc + s, tr + s, tc + s, s);
            }
        }
    }

2 2 3 3 
    2 1 1 3 
    4 1 5 5 
    4 4 5 0

# 第七章 动态规划介绍 #

动态规划（dynamic programming，dp）的核心思想是：将大问题划分为若干小问题进行解决，从而一步步获取最优解的处理算法。动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要他被计算过，就将其结果填入表中，这就是动态规划算法的基本思路。

# 第八章 动态规划应用 #

## 8.1、零一背包 ##

【描述】

一个旅行者有一个最多能装 M 公斤的背包，现在有 N 件物品，他们的重量分别是W1，W2，…，Wn，他们的价值分别为C1，C2，…，Cn，求旅行者能获得的最大总价值。

【输入】

第一行：两个整数，M(背包容量，M<=200)和N(物品数量，N<=30)；
    
    第2..N+1行：每行二个整数Wi，Ci，表示每个物品的重量和价值。

【输出】

仅一行，一个数，表示最大总价值。

【输入样例】

10 4
    2 1
    3 3
    4 5
    7 9

【输出样例】

【题目分析】

**第一步：根据题意建立对应表格，用来存放处理的解。**

![fe5760fe78612de5a757c48255ff56a5.png][]

**第二步：根据已知数据填表，推断出通用的递推表达式。**

*  填写第0行，默认全部为0，已经给出；
 *  填写第0列，默认全部为0，已经给出；

![990f4e1cd6f02d1dfc41211ff6669926.png][]

*  填写`dp[1][1]`，当前列的背包容量是1，而当前行的重量w为2，显然装不下，因此价值c为0；
 *  填写`dp[1][2]`，当前列的背包容量是2，而当前行的重量w为2，显然装得下，但是只有一个，因此价值c为1；
 *  填写`dp[1][3]`，当前列的背包容量是3，而当前行的重量w为2，显然装得下，但是只有一个，因此价值c为1；
 *  填写`dp[1][4]`，当前列的背包容量是4，而当前行的重量w为2，显然装得下，但是只有一个，因此价值c为1；
 *  填写`dp[1][5]`，当前列的背包容量是5，而当前行的重量w为2，显然装得下，但是只有一个，因此价值c为1；
 *  填写`dp[1][6]`，当前列的背包容量是6，而当前行的重量w为2，显然装得下，但是只有一个，因此价值c为1；
 *  填写`dp[1][7]`，当前列的背包容量是7，而当前行的重量w为2，显然装得下，但是只有一个，因此价值c为1；
 *  填写`dp[1][8]`，当前列的背包容量是8，而当前行的重量w为2，显然装得下，但是只有一个，因此价值c为1；
 *  填写`dp[1][9]`，当前列的背包容量是9，而当前行的重量w为2，显然装得下，但是只有一个，因此价值c为1；
 *  填写`dp[1][10]`，当前列的背包容量是10，而当前行的重量w为2，显然装得下，但是只有一个，因此价值c为1；

![71bdab8710e61728bce4f19ff02389f7.png][]

*  填写`dp[2][1]`，背包容量是1，重量w为3，显然装不下，此时上边还有一个重量为2的物品，这个装得下，因此价值c为`dp[2-1][1]=dp[1][1]=0`；
 *  填写`dp[2][2]`，背包容量是2，重量w为3，显然装不下，此时上边还有一个重量为2的物品，这个装得下，因此价值c为`dp[2-1][2]=dp[1][2]=1`；
 *  填写`dp[2][3]`，背包容量是3，重量w为3，显然装得下，此时上边还有一个重量为2的物品，3+2>背包容量，因此价值c为3。
 *  填写`dp[2][4]`，背包容量是4，重量w为3，显然装得下，此时上边还有一个重量为2的物品，3+2>背包容量，因此价值c为3。
 *  填写`dp[2][5]`，背包容量是5，重量w为3，显然装得下，此时上边还有一个重量为2的物品，3+2=背包容量，因此价值c为`dp[2-1][5-3]+3=4`。
 *  填写`dp[2][6]`，背包容量是6，重量w为3，显然装得下，此时上边还有一个重量为2的物品，3+2<背包容量，因此价值c为`dp[2-1][6-3]+3=4`。
 *  填写`dp[2][7]`，背包容量是7，重量w为3，显然装得下，此时上边还有一个重量为2的物品，3+2<背包容量，因此价值c为`dp[2-1][7-3]+3=4`。
 *  填写`dp[2][8]`，背包容量是8，重量w为3，显然装得下，此时上边还有一个重量为2的物品，3+2<背包容量，因此价值c为`dp[2-1][8-3]+3=4`。
 *  填写`dp[2][9]`，背包容量是9，重量w为3，显然装得下，此时上边还有一个重量为2的物品，3+2<背包容量，因此价值c为`dp[2-1][9-3]+3=4`。
 *  填写`dp[2][10]`，背包容量是10，重量w为3，显然装得下，此时上边还有一个重量为2的物品，3+2<背包容量，因此价值c为`dp[2-1][10-3]+3=4`。

![8c47018f4b38abe6b12ea245da847b81.png][]

填表格到了这里，我们就该发现一些规律了：

*  当`w[i]> 当前列背包重量j`，说明当前物品w的重量装不进去，所以用上一行对应列计算结果，也就是：`dp[i][j]=dp[i-1][j]`。
 *  当`w[i]<=当前列背包重量j`，说明当前物品w的重量装得进去，但有没有可能加上以前的重物，也就是：`max(dp[i-1][j],dp[i-1][j-w[i]]+c[i])`。

第一条规则比较好理解，第二条规则是什么鬼呢？当`w[i]<=当前列背包重量j`，说明此时的这个物品是可以装进背包中的，`j-w[i]`的意思是从当前背包中减去当前行`w[i]`的重量，`dp[i-1][j-w[i]]`看看剩下的容量在上一行中的计算的最大价值是多少，剩余的容量正好对应上一行的下标，然后在这个基础上加上当前行重物的价值`c[i]`。选出最大值`max(dp[i-1][j],dp[i-1][j-w[i]]+c[i])`填充到对应位置。按照这个策略依次进行下去，最终`dp[n][m]`存的就是旅行者能获得的最大总价值。

【代码实现】

public class Backpacker { 
        public static void main(String[] args) { 
            Scanner scanner = new Scanner(System.in);
            int m = scanner.nextInt();              //获取背包容量
            int n = scanner.nextInt();              //获取物品数量
            int[] w = new int[n + 1];               //定义重量数组
            int[] c = new int[n + 1];               //定义价值数组
            int[][] dp = new int[n + 1][m + 1];     //存储中间结果
    
            for (int i = 1; i <= n; i++) { 
                w[i] = scanner.nextInt();           //接收物品重量
                c[i] = scanner.nextInt();           //接收物品价值
            }
    
            for (int i = 1; i <= n; i++) {           //动态规划处理
                for (int j = 1; j <= m; j++) { 
                    if (w[i] > j) { 
                        dp[i][j] = dp[i - 1][j];
                    } else { 
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + c[i]);
                    }
                }
            }
    
            System.out.println(dp[n][m]);           //输出最终结果
        }
    }

【代码运行】

10 4
    2 1
    3 3
    4 5
    7 9
    12

【代码优化】

我们发现虽然使用了一个二维数组存储了每次运行的结果，但是当前行的结果会依赖上一行某列的结果，不依赖上上行或者上上上行某列的结果，那么，我们是不是可以使用一个一维数组来存储每次运行的结果，这显然是可行的，但是在存储的时候，我们不能从头按照顺序存储，因为那样会覆盖上一行某列的结果值，默认我们从后往前存储，这样就不会破坏上一行某列的结果值了，这样的代码优化，并没有减少时间复杂度，只是减少了空间复杂度，由于一维数组默认全部是0，这就为我们初始化好了第0行的结果了，具体代码只需要把关于`dp[i]`的下标全部删除，然后内层循环改为从后向前依次存储即可，最后`dp[m]`为最终解。

public class Backpacker2 { 
        public static void main(String[] args) { 
            Scanner scanner = new Scanner(System.in);
            int m = scanner.nextInt();              //获取背包容量
            int n = scanner.nextInt();              //获取物品数量
            int[] w = new int[n + 1];               //定义重量数组
            int[] c = new int[n + 1];               //定义价值数组
            int[] dp = new int[m + 1];              //存储中间结果
    
            for (int i = 1; i <= n; i++) { 
                w[i] = scanner.nextInt();           //接收物品重量
                c[i] = scanner.nextInt();           //接收物品价值
            }
    
            for (int i = 1; i <= n; i++) {           //动态规划处理
                for (int j = m; j >= 1; j--) { 
                    if (w[i] > j) { 
                        dp[j] = dp[j];
                    } else { 
                        dp[j] = Math.max(dp[j], dp[j - w[i]] + c[i]);
                    }
                }
            }
    
            System.out.println(dp[m]);              //输出最终结果
        }
    }

我们观察`if (w[i] > j)`这一句的判断是不是可以省去了，因为和`Math.max(dp[j], dp[j - w[i]] + c[i])`重复了，所以简化后：

public class Backpacker2 { 
        public static void main(String[] args) { 
            Scanner scanner = new Scanner(System.in);
            int m = scanner.nextInt();              //获取背包容量
            int n = scanner.nextInt();              //获取物品数量
            int[] w = new int[n + 1];               //定义重量数组
            int[] c = new int[n + 1];               //定义价值数组
            int[] dp = new int[m + 1];              //存储中间结果
    
            for (int i = 1; i <= n; i++) { 
                w[i] = scanner.nextInt();           //接收物品重量
                c[i] = scanner.nextInt();           //接收物品价值
            }
    
            for (int i = 1; i <= n; i++) {           //动态规划处理
                for (int j = m; j >= 1; j--) { 
                    if (w[i] <= j) { 
                        dp[j] = Math.max(dp[j], dp[j - w[i]] + c[i]);
                    }
                }
            }
    
            System.out.println(dp[m]);              //输出最终结果
        }
    }

【代码运行】

10 4
    2 1
    3 3
    4 5
    7 9
    12

## 8.2、完全背包 ##

【题目描述】

设有 N 种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为 M，今从 N 种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于 M，而价值的和为最大。

【输入】

第一行：两个整数，M(背包容量，M≤200)和N(物品数量，N≤30)；
    
    第2..N+1行：每行二个整数Wi,Ci，表示每个物品的重量和价值。

【输出】

仅一行，一个数，表示最大总价值。

【输入样例】

10 4
    2 1
    3 3
    4 5
    7 9

【输出样例】

【题目分析】

我们已经学过了零一背包问题，但是在零一背包中，每件物品要不可以拿，要不可以不拿，就只有这两种选择。而完全背包强调的是每件物品是无限的，也就是说，我们尽量选择物品最重的，价值最大的，这样，每次我们就不用选择上一行某列计算的价值，而是使用背包容量减去当前重物w的重量，剩余的重量不去上一行的某列数据取值，而是在当前行某列数据取值，因此推导公式需要修改，具体对比：

![82a38702a46d4039c14e5980eee782db.png][]

【代码实现】

public class Backpacker3 { 
        public static void main(String[] args) { 
            Scanner scanner = new Scanner(System.in);
            int m = scanner.nextInt();              //获取背包容量
            int n = scanner.nextInt();              //获取物品数量
            int[] w = new int[n + 1];               //定义重量数组
            int[] c = new int[n + 1];               //定义价值数组
            int[] dp = new int[m + 1];              //存储中间结果
    
            for (int i = 1; i <= n; i++) { 
                w[i] = scanner.nextInt();           //接收物品重量
                c[i] = scanner.nextInt();           //接收物品价值
            }
    
            for (int i = 1; i <= n; i++) {           //动态规划处理
                for (int j = 1; j <= m; j++) { 
                    if (w[i] <= j) { 
                        dp[j] = Math.max(dp[j], dp[j - w[i]] + c[i]);
                    }
                }
            }
    
            System.out.println(dp[m]);              //输出最终结果
        }
    }

【代码运行】

10 4
    2 1
    3 3
    4 5
    7 9
    12

# 第九章 贪心算法介绍 #

贪心算法（greedy algorithm）又称贪婪算法，是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。

# 第十章 贪心算法应用 #

## 10.1、分发饼干 ##

【题目描述】

有一群孩子和一堆饼干，每个孩子有一个饥饿度，每个饼干都有一个大小。每个孩子只能吃最多一个饼干，且只有饼干的大小大于孩子的饥饿度时，这个孩子才能吃饱。求解最多有多少孩子可以吃饱。

【输入】

输入两个数组，分别代表孩子的饥饿度和饼干的大小。

【输出】

输出最多有多少孩子可以吃饱的数量。

【样例1】

输入: g = [1,2,3], s = [1,1]
    输出: 1
    解释: 
    你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
    虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
    所以你应该输出1。

【样例2】

输入: g = [1,2], s = [1,2,3]
    输出: 2
    解释: 
    你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
    你拥有的饼干数量和尺寸都足以让所有孩子满足。
    所以你应该输出2。

【题目分析】

因为饥饿度最小的孩子最容易吃饱，所以我们先考虑这个孩子。为了尽量使得剩下的饼干可以满足饥饿度更大的孩子，所以我们应该把大于等于这个孩子饥饿度的、且大小最小的饼干给这个孩子。满足了这个孩子之后，我们采取同样的策略，考虑剩下孩子里饥饿度最小的孩子，直到没有满足条件的饼干存在。简而言之，这里的贪心策略是，给剩余孩子里最小饥饿度的孩子分配最小的能饱腹的饼干。至于具体实现，因为我们需要获得大小关系，一个便捷的方法就是把孩子和饼干分别排序。这样我们就可以从饥饿度最小的孩子和大小最小的饼干出发，计算有多少个对孩子可以满足条件。

【代码实现】

public class AssignCookies { 
        public static void main(String[] args) { 
            int[] g1 = { 1, 2, 3};
            int[] s1 = { 1, 1};
            System.out.println(findContentChildren(g1, s1));
    
            int[] g2 = { 1, 2};
            int[] s2 = { 1, 2, 3};
            System.out.println(findContentChildren(g2, s2));
        }
    
        //核心代码
        public static int findContentChildren(int[] children, int[] cookies) { 
            Arrays.sort(children);  //从小到大升序排序孩子饥饿度
            Arrays.sort(cookies);   //从小到大升序排序饼干的大小
            int child = 0;          //能吃饱的孩子下标
            int cookie = 0;         //被分配的饼干下标
    
            while (child < children.length && cookie < cookies.length) { 
                if (children[child] <= cookies[cookie++]) { 
                    child++;
                }
            }
    
            return child;
        }
    }

【代码运行】

1
    2

## 10.2、广播覆盖 ##

【题目描述】

假设存在如下表的需要付费的广播台，以及广播台信号可以覆盖的地区。如何选择最少的广播台，让所有的地区都可以接收到信号。

![449fc38af190ca7b6fd2142ebee226cd.png][]

通过上述广播台和覆盖地区的对应关系，可以获取所有覆盖地区：`北京，上海，天津，广州，深圳，成都，杭州，大连`。

【题目分析】

![ea233d0c7661234d0da2d3e6c4adb49a.png][]

【代码实现】

public class BroadcastCoverage { 
        public static void main(String[] args) { 
            //创建广播电台集合
            HashMap<String, HashSet<String>> broadcasts = new HashMap<>();
    
            //将各个电台存起来
            HashSet<String> broadcast1 = new HashSet<>();
            broadcast1.add("北京");
            broadcast1.add("上海");
            broadcast1.add("天津");
            broadcasts.put("K1", broadcast1);
            HashSet<String> broadcast2 = new HashSet<>();
            broadcast2.add("广州");
            broadcast2.add("北京");
            broadcast2.add("深圳");
            broadcasts.put("K2", broadcast2);
            HashSet<String> broadcast3 = new HashSet<>();
            broadcast3.add("成都");
            broadcast3.add("上海");
            broadcast3.add("杭州");
            broadcasts.put("K3", broadcast3);
            HashSet<String> broadcast4 = new HashSet<>();
            broadcast4.add("上海");
            broadcast4.add("天津");
            broadcasts.put("K4", broadcast4);
            HashSet<String> broadcast5 = new HashSet<>();
            broadcast5.add("杭州");
            broadcast5.add("大连");
            broadcasts.put("K5", broadcast5);
    
            //存放被覆盖的地区
            HashSet<String> allAreas = new HashSet<String>();
            allAreas.addAll(broadcast1);//会自动去除重复元素
            allAreas.addAll(broadcast2);//会自动去除重复元素
            allAreas.addAll(broadcast3);//会自动去除重复元素
            allAreas.addAll(broadcast4);//会自动去除重复元素
            allAreas.addAll(broadcast5);//会自动去除重复元素
    
            //输出最后选择结果
            System.out.println(selectBroadcasts(broadcasts, allAreas));
        }
    
        //核心代码
        public static ArrayList<String> selectBroadcasts(HashMap<String, HashSet<String>> broadcasts, HashSet<String> allAreas) { 
            ArrayList<String> selects = new ArrayList<>();      //存放选择电台集合
            HashSet<String> tempSet = new HashSet<>();          //存放电台覆盖地区和当前还没有覆盖地区的交集
            while (allAreas.size() != 0) {                       //只要当前的地区集合没有被全部覆盖就接着循环
                String maxKey = null;                           //存放能够覆盖最大未覆盖的地区对应电台的key
                for (String key : broadcasts.keySet()) { 
                    tempSet.clear();                            //清空掉tempSet
                    HashSet<String> areas = broadcasts.get(key);
                    tempSet.addAll(areas);                      //添加到tempSet
                    tempSet.retainAll(allAreas);                //获取tempSet和allAreas的交集然后放到tempSet
                    if (tempSet.size() > 0 && (maxKey == null || tempSet.size() > broadcasts.get(maxKey).size())) { 
                        maxKey = key;
                    }
                }
                if (maxKey != null) {                            //如果这次找到最大key
                    selects.add(maxKey);                        //添加到选择电台集合
                    allAreas.removeAll(broadcasts.get(maxKey)); //删除已覆盖电台地区
                }
            }
            return selects;
        }
    }

【代码运行】

[K1, K2, K3, K5]

[3771c63d1c85d013fc8c28e80a9a7135.png]: /images/20221023/3872d0f0b16c4c8a8e4e257faec41469.png
[035e9d23b7dc52c12086925e47901fb5.png]: /images/20221023/9599fe6d583247c6bca510766c3e1ec4.png
[d79affc5047ec1e21c4a70e009ad2f76.png]: /images/20221023/132dea34c629493a9d82ec9fde2c0ff1.png
[04006cdda0c21c100a4fed4a8c16ad19.png]: /images/20221023/6bef50ccaea7482eb90a80cfd53d3a39.png
[6c4b938d6a1e35309efd7086f6e1dbad.png]: /images/20221023/921b4a08bc174c8d87b5b7a3cb23f152.png
[203227f275814b3a14cadb9142b3eb9a.png]: /images/20221023/4c91e7147cd241bb97a1d5c5e8845a06.png
[6e02171824eb5f59753604fea911fada.png]: /images/20221023/c224ea6426154e07996b07b348ed39a3.png
[ac6f6bb3e870da9d85439474a54f4b1e.png]: /images/20221023/8c80ea00bf3040c3845b98d596bbe235.png
[bdf6976cca628cc345719dc64c47b435.png]: /images/20221023/7c454c59a5e140d19a3dbdab1e4c2f5c.png
[ce467b2fab1d4b0a9e3f664c46a97157.png]: /images/20221023/cd010cc2a6054b688254925a39b386e1.png
[cb050b21e080e5b3d180216eaae7acab.png]: /images/20221023/73d3b182ec0c4d1f904d814c587602c7.png
[4e63c98cb4eda11b3a3458fa8282cac5.png]: /images/20221023/32ca1c3a3a4d435c8b2cf64f1d8eb0dc.png
[c4b34f9d62b2b4818673016c19675f91.png]: /images/20221023/efb9da28dbf7466b82f45553805e3400.png
[f26a3642ea9799a6b3c449e8eba8b307.png]: /images/20221023/9652e9b8390843a388e2dd429012bbf0.png
[762451ef9e4f95e61a3555219db85216.png]: /images/20221023/63b7cf69ab89442e8ed543d4bfe4c134.png
[462e0ede3b54626cc9f4b769231e6139.png]: /images/20221023/21ab3bcc43924b6c999ec8a74066e3fe.png
[67aceddde4e56fc82c4881ba2e10aabf.png]: /images/20221023/a17d326ec20145eeb783c673b95bbc3f.png
[6ee4f107d198f188152353fcacf07af2.png]: /images/20221023/b3375b0889074c9e851b79526740ae8a.png
[4a4fa717f89d4b4df51856d74cf69116.png]: /images/20221023/b48b35a28417406895f62ebd84d8aa84.png
[cdb944a8acaac03d7f411159b99a7632.png]: /images/20221023/f8205e98151b4296b7dca46e4303ac2e.png
[7d331074d6fe175a1d4db64ddef59aae.png]: /images/20221023/00f699ebc6a5460c8fbcee3b96d309c9.png
[407e871b61d0423c5d754fc882cfd8de.png]: /images/20221023/ecfae95dfe534014bd88767d63069d5d.png
[e0e8b42548b7a426ba6fa3639247d67d.png]: /images/20221023/b05e97f9479447d0a61cea7daaf3e5c8.png
[0ef16e3b91f624f76e50aacf6ef89b74.png]: /images/20221023/389fb2a00c6c418f90805546e737c42c.png
[4c83c05c958c274b24f11b6654319b80.png]: /images/20221023/9f5d8fab6a1f4d67a4ae45b297eab7c8.png
[735447c165aec945ccaddb489660637c.png]: /images/20221023/2af18cd5ce214788a02aaf94b33cd9e7.png
[fe5760fe78612de5a757c48255ff56a5.png]: /images/20221023/8811c3216eae46d8a963e128fd52998b.png
[990f4e1cd6f02d1dfc41211ff6669926.png]: /images/20221023/4fccb873d90c40a183daef0462118ed7.png
[71bdab8710e61728bce4f19ff02389f7.png]: /images/20221023/1e36c1c60eef4f3594c5ac214e1822d0.png
[8c47018f4b38abe6b12ea245da847b81.png]: /images/20221023/970365d769134e97aaca4684580f1ff7.png
[82a38702a46d4039c14e5980eee782db.png]: /images/20221023/5ed1e029467845189af183756b8447dc.png
[449fc38af190ca7b6fd2142ebee226cd.png]: /images/20221023/353375c79815431dabfb3a5f1af6f607.png
[ea233d0c7661234d0da2d3e6c4adb49a.png]: /images/20221023/e6a8b13cd5b44694a38fdf8797001c49.png