没有人永远年轻，但是永远有人年轻

算法笔记

动态规划实在是太牛逼了 拿到题目：考虑能不能使用动态规划

马拉车算法

解决的问题：寻找字符串的最长回文子串
特点：线性时间复杂度O(N)

我的分析

给出字符串：abccba

先逆向思维：
如果我有一个数组p，它和原始字符串等长， 里面存放的是以该索引下的字符为中心的 回文串的长度，那么求出回文串就很容易了， 那么该如何构这个数组p？

0	1	2	3	4
c	b	c	b	c
1	2	3	2	1

二分查找

• 迭代：

while(l<r){
    int mid = (l+r)/2;
    ...
}

• 递归

f(l,r){
    int mid = (l+r)/2;
    f(l,mid);
    f(mid,r);
}

回溯算法

回溯要按树的思维来理解

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择