常见算法总结

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

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

一.蛮力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]$;

1
2
3
4
5
6
7
8
9
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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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.

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

目的:可以优化空间复杂度,不知道可以不可以优化时间复杂度

四.贪心

短视,局部最优(少考虑很多,计算量就下去了)

需要证明

五.回溯

一般用于可以用树型结构建模的问题

回溯法能系统地搜索一个问题的所有解,和暴力的区别在于回溯可以剪枝,以此减少计算量

实现方式:利用DFS搜索解空间,一般递归实现

https://zhuanlan.zhihu.com/p/93530380

https://zhuanlan.zhihu.com/p/112926891

六.分支限界

类似回溯,区别如下

代价函数

以极大值问题为例,以当前结点为根的子树能够得到的可行解的最大值

以极大值问题为例,当前已经得到的可行解的最大值

减枝

代价函数和界可以用于减枝,以极大值问题为例,界大于等于某结点代价函数,该结点就不需要继续搜索了

参考文献

https://blog.csdn.net/zm1_1zm/article/details/69224626

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

https://segmentfault.com/a/1190000038223084

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

Author

Lavine Hu

Posted on

2021-07-24

Updated on

2024-06-20

Licensed under

# Related Post
  1.双指针
  2.递归
  3.递归,迭代
  4.basic algorithm
  5.dfs,bfs
  6.时间复杂度计算
Comments

:D 一言句子获取中...