记几道BFS，中心扩展法，动态规划，状态压缩的例题

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

目录

前言

一、中心扩展法

二、BFS

三、状态压缩

 四、动态规划

总结

---

前言

提示：这里可以添加本文要记录的大概内容：

在学习数据结构的时候学到了不少算法思想，但是那时候真的很难，直到现在发现有些算法思想不懂不行，所以去刷了不少题，在此记录下印象比较深的题。

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、中心扩展法

1、个人理解：中心扩展法的思想就是在解决某个事情的时，以某点为中心，向着左右两边扩散，直至某个条件不满足或满足时再返回结果，或者以下一个点为中心继续进行相同的扩展运算。

2、例题：最长回文字符串

题目简介：在一个英文字符串L中，找出最长的回文字符串，如L="caayyhheehhbbbhhjhhyyaac"，那么它最长的回文字串是"hhbbbhh"，L的长度可能接近10的4次方，要考虑时间和空间复杂度的问题。

自己想的时候：能不能使用暴力的做法，直接遍历所有的子字符串，从所有的子字符串中判断回文的字符串，然后从回文字符串中返回长度最大的。再仔细想想，L的长度可能接近10的4次方，那么子字符串就有2^(10^4)-1种，还要判断这么多种字符串是否回文，时间消耗必然很大。

最优解法：中心扩展法

分析题目：题目包含的情况其实有以下几种

第一种：当字符串只有1个的极端情况，则直接返回本身即可

第二种：以某个字符串为中心，在不超出索引的情况下向两边扩展，假若中心点的字符与左边一个或右边一个字符相等，则中心字符串往后移一位，回文字符串长度+1。比如"abcmm"，以m为中心点时，右边字符与它相等，则mm就是一个回文字符串，中心点往后移，长度+1。

第三种：第二种情况不符合的情况下，比如"abcdca"，当从a开始为中心扩散，中心到c时，判断左边一个字符是否和右边一个字符相等，相等则回文长度+2，继续往左边和右边的第二个遍历，直到不满足情况就返回。

最终：在不超过索引的情况下，遍历字符串，以每个字符会中心，进行扩散，记录最大的回文字符串长度即可，这样即使L的长度可能接近10的4次方，也只需要遍历10^4次。

代码：

def max_Palindrome_string(s):
    length = len(s)
    # 判断字符串的极端情况
    if length == 1:
        return s
    elif length == 2 and s[0] != s[1]:
        return s[0]
    elif length == 2 and s[0] == s[1]:
        return s
    max_len = 1
    max_str = s[0]
    for i in range(length):  # 以每个字符为中心进行左右扩散
        cur_len = 1  # 记录当前回文字符串的长度
        right = i + 1  # 右边字符
        left = i - 1  # 左边字符
        while left >= 0 and s[i] == s[left]:  # 第二种情况,当前字符和左边一个相等或者右边一个相等,则往当前字符往后移一个,回文字符长度+1
            cur_len += 1
            left -= 1
        while right < length and s[i] == s[right]:
            cur_len += 1
            right += 1
        while right < length and left >= 0 and s[right] == s[left]:  # 第三种情况,当第二种情况不相等,左边字符等于右边字符,回文字符长度+2
            cur_len = cur_len + 2
            right = right + 1
            left = left - 1
        left += 1  # 不满足循环后left+1,记录回文字符字串最左边的标记
        if cur_len > max_len:  # 当前回文字符串长度与记录到的最大回文长度比较
            max_len = cur_len
            max_str = s[left:left + max_len]  # 返回最大的回文字符串
    return max_str


if __name__ == '__main__':
    string = 'caayyhheehhbbbhhjhhyyaac'
    print(max_Palindrome_string(string))

二、BFS

1、个人理解：以图的路径搜索来讲，BFS就以节点的方法搜索遍历图的所有路径，返回需要的结果。

2、例题：

一马当先：马只能走'日'字形（包括旋转90°的日），现在想象一下，给你一个n行m列网格棋盘， 棋盘的左下角有一匹马，请你计算至少需要几步可以将它移动到棋盘的右上角。

题目分析：马走日，一种有多少种情况呢，左上，左下，右上，右下，日也可以是躺着的日，一共有8种情况，以二维坐标轴表示，假如马在中心(0,0)点，那么马就只能跳到(2，-1)，（1，-2），（-1，-2），（-2，-1），（-2，1），（-1，2），（1，2），（2，1）八种情况。那么就可以使用BFS思想，让马从（0，0）起跳，跳八种情况，然后将跳后的八个点作为起跳，继续每个点都跳八种情况，将所有情况搜寻出来，直至马到达右上角结束返回。

代码如下:

def BFS_all_step(m, n):
    x = [+2, +1, -1, -2, -2, -1, +1, +2]
    y = [-1, -2, -2, -1, +1, +2, +2, +1]
    temp = [set(), {(0, 0)}, set()]  # 分别代表上一跳,当前跳,下一跳
    t = 1  # 记录移动的步数
    f = True
    while f:
        f = False
        for loc in temp[1]:  # 从当前跳为起跳点,遍历跳上述的八种情况
            for i in range(8):  # 跳八种可能的情况
                x = loc[0] + x[i]
                y = loc[1] + y[i]
                if (x, y) == (m, n):  # 如果刚好跳到右上角,则结束返回
                    return t
                elif 0 <= x <= m and 0 <= y <= n and not (
                        (x, y) in temp[0] or (x, y) in temp[1] or (x, y) in temp[2]):  # 还在棋盘内并且确保跳的路径不重复
                    temp[2].add((x, y))  # 记录下一跳的所有结果
                    f = True
        t += 1  # 还没跳到右上角,步数+1
        del temp[0]  # 将下一跳的结果变成当前跳的位置,当前跳变成上一跳的结果
        temp.append(set())  # 将下一跳设置为空
    return -1  # 所有情况都没有达到右上角，返回-1


if __name__ == '__main__':
    m = 5
    n = 3
    print(BFS_all_step(m, n))

三、状态压缩

1、个人理解：状态压缩的思想指的是按照意思先定义一个初始满足条件的值，然后对值进行压缩，全部压缩结束后，判断被压缩后的值是否符合并返回结果。

2、例题：

正方形拼接：现在有一堆木棒，告诉你它们的长度，判断能否用这些木棒拼接成正方形。 
注意：所有的木棒都要用上，且不能截断。 给你一个正整数list L, 如 L=[1,1,1,1],
L中的每个数字代表一个木棒的长度，如果这些 木棒能够拼成一个正方形，
输出Yes，否则输出No。 如L=[1,1,1,1]，则输出Yes;L=[1,1,1],则输出No。

题目分析：

首先，要符合木棍能够拼接成正方形，木棍的总长度必定是4的倍数，每条边的长度为总木棍长度/4，也就是每条边的长度是固定的，最长的木棍必定要拼接到当前最短的边中才有可能拼接成四条边相等，因此可以将四条边初始状态定为总长度/4，通过用最大的长度减去最长的木棍对初始状态进行压缩，若有边长度相同则随意选一条，直至木棍减完，所有边被压缩为0，则代表可以组成正方形。

代码如下：

L = [4, 5, 3, 2, 9, 1, 3, 8, 1, 6, 5, 1]
L.sort()
sum_L = sum(L)

if sum_L % 4 != 0 or not sum_L:  # 判断木棍的是否为4个倍数，不是则不可能拼接成正方形
    print("No")
else:
    square_list = [sum_L // 4] * 4  # 建立4个数的列表，每个数长度为总长度/4
    while L:
        square_list[3] -= L.pop()  # 将最长的木棍拼接到最短的边中
        square_list.sort()  # 再对列表排序,便于上面求剩余最多的边
    if not min(square_list):
        print('Yes')
    else:
        print('No')

 四、动态规划

1、个人理解：动态规划大多用于求在许多解中找到最优解的一种方法，将一个问题分解成多个子问题，通过利用子问题的结果继续运算叠加，计算出最终的结果。

2、题目：

最大非连续子序列：给你一个整数list L, 如 L=[2,-3,3,50], 求L的一个非连续子序列，使其和最大，输出最大子序列的和。这里非连续子序列的定义是，子序列中任意相邻的两个数在原序列里都不相邻。例如，对于L=[2,-3,3,50]， 输出52（分析：很明显，该列表最大非连续子序列为[2,50])

题目分析：非连续子序列相加的结果有很多，要在众多结果中求出最大的，可以使用动态规划。

也就说，要确认L[i+1]个位置的最大非连续子序列和，与L[i-1]位置前求到的最大子序列的结果与L[i+1]相加即可。

代码如下:

L = [2, 3, -3, 50]
L = [0] + L
print(L)
for i, value in enumerate(L):
    if i > 1:  # 索引为1前的最大非连续子序列为本身,从索引为2开始算起
        L[i] = L[i] + max(L[:i - 1])  # 求第L[i]个非连续子序列和,将L[i]与L[i-1]前的最大非连续子序列和相加即可
print(max(L))

---

总结

许多算法听起来貌似非常简单，但当遇到具体的题目要解决，真的不容易，甚至乎看着别人的代码看半天都不懂，只能一步一步debug，弄清楚算法的每一个步骤的意思，才能很好的理解，还得努力。