2021-07-24 b252747dca4de404ee2b0a8063b40954 99+ 8 m 1.2 k

常见算法总结

类别归类：蛮力，分治，动态规划，贪心，回溯，分支限界。

实现方式有两种，一般为基于迭代和基于递归。

一.蛮力Brute-force

没有什么好说，就是遍历或者枚举。

二.分治

分而治之，将大问题拆解成相互独立且相似的子问题。

步骤：1、先分 2 求解 3 .合并

实现方式：一般递归实现

三.动态规划

和暴力相比，dp利用了子问题间的依赖关系，减少了一些计算

适用条件：1.满足最优子结构性质，即最优解所包含的子问题的解也是最优的

构造递推式：

0.确定维度，一般一维或者二维

1.注意含义

2.选择分隔点

a. 一般和前一步或者两步有关,比如最大子序和，$dp[i]=max(s[i],s[i]+dp[i-1])$

b. 但有时候需要遍历全部分割点，比如单词拆分，$dp[i]=dp[j] \ \& \& \ check(s[j..i−1])$，

c. 有时候动态选择分隔点，比如丑数，$ dp[i]=min(dp[p2]2,dp[p3]3,dp[p5]*5) $,其中$p2,p3,p5$动态变化

3.注意+， -

一定是用已有的递推没有的

举例比如62. 不同路径，$dp[i][j] = dp[i-1][j] + dp[i][j-1]$；

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1]*n] + [[1]+[0] * (n-1) for _ in range(m-1)]
        #print(dp)
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[-1][-1]

比如5. 最长回文子串，$dp[i][j]=dp[i+1][j-1] \ and \ s[i]==s[j]$

s = “babad”

n=5

（i，j）

(0,1) (1,2) (2,3) (3,4) (0,2) (1,3) (2,4) (0,3)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:
            return s
        
        max_len = 1
        begin = 0
        # dp[i][j] 表示 s[i..j] 是否是回文串
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = True
        
        # 递推开始
        # 先枚举子串长度
        for L in range(2, n + 1):
            # 枚举左边界，左边界的上限设置可以宽松一些
            for i in range(n):
                # 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                j = L + i - 1
                # 如果右边界越界，就可以退出当前循环
                if j >= n:
                    break
                    
                if s[i] != s[j]:
                    dp[i][j] = False 
                else:
                    if j - i < 3:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i + 1][j - 1]
                
                # 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if dp[i][j] and j - i + 1 > max_len:
                    max_len = j - i + 1
                    begin = i
        return s[begin:begin + max_len]

解的追踪：有时候需要借助备忘录搜索解，时间复杂度不超过计算备忘录

实现方式

递归实现：效率不高的原因在于子问题重复计算了，比起暴力哪个快？应该还是这个

迭代+备忘录：不一定全部都要存储，需要的存着了就可以了，每次子问题计算一次（空间换时间）

一般采用迭代+备忘录

状态压缩动态规划

https://jimmy-shen.medium.com/bitmask-state-compression-dp-39e7ba56978b

https://segmentfault.com/a/1190000038223084

https://blog.csdn.net/wxgaws/article/details/114693162

Usually, the state of DP can use limited variables to represent such a dp[i] , dp[i] [j] ,dp[i] [j] [k].

However, sometimes, the states of a DP problem may contain multiple statuses. In this case, we can think about using the state compression approaches to represent the DP state.

说白了就是在状态很多的时候对状态降维

目的：可以优化空间复杂度，不知道可以不可以优化时间复杂度