Leetcode部分递归、回溯、分治、动态规划相关练习

一、 递归二、回溯1.回溯的概念2. 回溯相关练习51.N皇后利用回溯算法求解 0-1 背包问题 三、分治1.分治的概念2.分治算法的基本步骤3.分治相关练习利用分治算法求一组数据的逆序对个数 四、动态规划1. 动态规划的概念2.基本思想与策略3. 适用的情况4.动态规划相关练习利用动态规划求解 0-1 背包问题64. 最小路径和72. 编辑距离编程实现查找两个字符串的最长公共子序列673. 最长递增子序列的个数（编程实现一个数据序列的最长递增子序列） 五、练习实战递归：17. 电话号码的字母组合46. 全排列 实战DP（动态规划）132. 分割回文串 II10. 正则表达式匹配322. 零钱兑换121. 买卖股票的最佳时机152. 乘积最大子序列120. 三角形最小路径和

一、 递归

https://blog.csdn.net/weixin_41725746/article/details/90241793.

二、回溯

1.回溯的概念

1.回溯算法就是一种有组织的系统最优化搜索技术，可以看作蛮力法穷举搜索的改进。回溯法常常可以避免搜索所有可能的解，所以它适用于求解组织数量较大的问题。

2.解空间树： 问题的解空间一般使用解空间树的方式来组织，树的根节点位于第1层，表示搜索的初始状态，依次向下排列。

3.解空间树的动态搜索： 在搜索至树中任一节点时，先判断该节点对应的部分是否是满足约束条件，或者是否超出目标函数的界，也就是判断该节点是否包含问题的最优解。如果肯定不包含，则跳过对该节点为根的子树的搜索，即所谓的剪枝；否则，进入该节点为根的子树，继续按照深度优先策略搜索。（这也是为什么回溯可以避免搜索所有的解）

4.在搜索过程中，通常采用两种策略避免无效搜索： （1）用约束条件剪除得不到的可行解的子树 （2）用目标函数剪取得不到的最优解的子树 （这两种方式统称为：剪枝函数）

5.在用回溯法求解问题时，常常遇到两种典型的解空间树： （1）子集树：但所有的问题是从n个元素的集合中找出满足某种性质的子集时，相应的解空间树成为子集树 （2）排列树：当所给出问题是确定n个元素满足某种性质的排列时，相应的解空间称为排列树。

6.回溯法的一般步骤： （1）设置初始化的方案（给变量赋初始值，读入已知数据等） （2）变换方式去试探，若全部试完侧转（7） （3）判断此法是否成功（通过约束函数），不成功则转（2） （4）试探成功则前进一步再试探 （5）正确方案还是未找到则转（2） （6）以找到一种方案则记录并打印 （7）退回一步（回溯），若未退到头则转（2） （8）已退到头则结束或打印无解

7.回溯法的优点在于其结构明确，可读性强，易于理解，而且通过对问题的分析可以大大提高运行效率。

2. 回溯相关练习

51.N皇后

https://leetcode-cn.com/problems/n-queens/ 问题描述： n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 上图为8皇后问题的一种解法。 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。 示例：

输入: 4 输出: [ [".Q…", // 解法 1 “…Q”, “Q…”, “…Q.”], ["…Q.", // 解法 2 “Q…”, “…Q”, “.Q…”] ] 解释: 4 皇后问题存在两个不同的解法。

解题思路： 1、从1行开始，逐行扫描，避免了同行判断； 2、针对每一行的扫描，枚举列的全部可能； 3、剪枝的要点，判断同列、判断斜向左下和右上（x + y固定）、判断斜向右下和左上（x-y固定）；

代码实现

class Solution: def solveNQueens(self, n: int) -> List[List[str]]: res = [] s = "." * n def backtrack(i, tmp,col,z_diagonal,f_diagonal): if i == n: res.append(tmp) return for j in range(n): if j not in col and i + j not in z_diagonal and i - j not in f_diagonal: backtrack(i+1,tmp + [s[:j] + "Q" + s[j+1:]], col | {j}, z_diagonal |{i + j} , f_diagonal |{i - j} ) backtrack(0,[],set(),set(),set()) return res

利用回溯算法求解 0-1 背包问题

问题描述： 给定N个物品和一个背包。物品i的重量是Wi,其价值位Vi ，背包的容量为C。问应该如何选择装入背包的物品，使得放入背包的物品的总价值为最大？ 代码实现：

bestV=0 curW=0 curV=0 bestx=None def backtrack(i): global bestV,curW,curV,x,bestx if i>=n: if bestV<curV: bestV=curV bestx=x[:] else: if curW+w[i]<=c: x[i]=True curW+=w[i] curV+=v[i] backtrack(i+1) curW-=w[i] curV-=v[i] x[i]=False backtrack(i+1) if __name__=='__main__': n=5 c=10 w=[2,2,6,5,4] v=[6,3,5,4,6] x=[False for i in range(n)] backtrack(0) print(bestV) # 15 print(bestx) # [True, True, False, False, True

三、分治

1.分治的概念

在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……

2.分治算法的基本步骤

分治法在每一层递归上都有三个步骤：

step1 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

step2 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题

step3 合并：将各个子问题的解合并为原问题的解。

3.分治相关练习

利用分治算法求一组数据的逆序对个数

摘自：https://blog.csdn.net/contr4l_/article/details/80611675 题目描述： 对于一个序列a1,a2,a3…an, 若存在i,j，使得i<j且ai>aj，则称为一个逆序对

输入： 一个list对象 输出： list中逆序对数目

解题思路： 一个朴素的想法是这样的：依次遍历list中每一个元素，对每一个元素，查找其之后的每一个元素并与其比较，出现逆序对则计数+1，时间复杂度为O(n^2)——(n-1)+(n-2)+…+1。

但对于这个算法，实际上有隐含的条件被我们忽略了，例如当我们发现a2<a1时，那么对于和a2比较过的所有元素，与a2形成逆序对的所有元素实际上也与a1形成逆序对（除a2外），实际上时间复杂度可以精简到O(nlogn)。

我们可以换一个思路来考虑这个问题：对于一个a1<a2<a3…<an的有序序列，逆序对是为0的，那么我们实际上是要进行一个排序，当发现一次逆序，计数+1，而排序算法的最优解法为O(nlogn)

代码实现：

def Count(lst1, lst2,count): i = 0 j = 0 res = [] while i < len(lst1) and j < len(lst2): if lst1[i] <= lst2[j]: res.append(lst1[i]) i += 1 else: res.append(lst2[j]) count += len(lst1)-i # 当右半部分的元素先于左半部分元素进入有序列表时，逆序对数量增加左半部分剩余的元素数 j += 1 res += lst1[i:] res += lst2[j:] return res,count def InversionNum(lst): # 改写归并排序,在归并排序中，每当R部分元素先于L部分元素插入原列表时，逆序对数要加L剩余元素数 if len(lst) == 1: return lst,0 else: n = len(lst) // 2 lst1,count1 = InversionNum(lst[0:n]) lst2,count2 = InversionNum(lst[n:len(lst)]) lst,count = Count(lst1,lst2,0) return lst,count1+count2+count print(InversionNum([11,10,9,8,7,6,5,4,3,2,1])) # 输出为：[1,2,3,4,5,6,7,8,9,10,11] 55

四、动态规划

摘自https://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741374.html

1. 动态规划的概念

动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。

2.基本思想与策略

基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。

与分治法最大的差别是： 适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。

3. 适用的情况

能采用动态规划求解的问题的一般要具有3个性质：

(1) 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。(2) 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。（3）有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）

4.动态规划相关练习

利用动态规划求解 0-1 背包问题

问题描述： 给定N个物品和一个背包。物品i的重量是Wi,其价值位Vi ，背包的容量为C。问应该如何选择装入背包的物品，使得放入背包的物品的总价值为最大？ 解题思路： ①不超过背包容量，有：Σw[i]<=C (i表示第i件物品); ②对于“将前i件物品放入容量为j的背包中”这个子问题，现只考虑第i件物品放还是不放，如果放了的话，问题转换为“前i-1件物品放入剩下j-w[i]容量的背包中”，如果不放，问题转换为“前i-1件物品放入容量为j的背包中”。这两种情况的优者为当前问题的最优解； ③根据②的分析，得到如下递推公式： 其中，0<=i<=N,0<=j<=W. ④例子 5个物品的重量和价值分别为（5，12），（4，3），（7，10），（2，3），（6，6），背包容量15。

初始化表: 根据公式填表: 随便选一个来分析，比如上表圈中位置f[3][9]表示前3件物品放入容量为9的背包中，最高价值为15

15如何来的呢？ 考虑第三件物品放还是不放入背包，若放入背包f[3][9]=f[2][9-w[3]]+v[3]=f[2][2]+v[3]=0+10=10 若不放入背包，f[3][9]=f[2][9]=15 因为15>10，所有第三件物品不放入背包，前3件物品放入容量为9的背包得到的最高价值是15

代码实现：

def bag(n, c, w, v): """ 测试数据： n = 5 物品的数量， c = 15 书包能承受的重量， w = [5, 4, 7, 2, 6] 每个物品的重量， v = [12, 3, 10, 3, 6] 每个物品的价值 """ # 置零，表示初始状态 value = [[0 for j in range(c + 1)] for i in range(n + 1)] for i in range(1, n + 1): for j in range(1, c + 1): value[i][j] = value[i - 1][j] # 背包总容量够放当前物体，遍历前一个状态考虑是否置换 if j >= w[i - 1] and value[i][j] < value[i - 1][j - w[i - 1]] + v[i - 1]: value[i][j] = value[i - 1][j - w[i - 1]] + v[i - 1] for x in value: print(x) return value def show(n, c, w, value): print('最大价值为:', value[n][c]) x = [False for i in range(n)] j = c for i in range(n, 0, -1): if value[i][j] > value[i - 1][j]: x[i - 1] = True j -= w[i - 1] print('背包中所装物品为:') for i in range(n): if x[i]: print('第', i+1, '个,', end='') def bag1(n, c, w, v): values = [0 for i in range(c+1)] for i in range(1, n + 1): for j in range(c, 0, -1): # 背包总容量够放当前物体，遍历前一个状态考虑是否置换 if j >= w[i-1]: values[j] = max(values[j-w[i-1]]+v[i-1], values[j]) return values if __name__ == '__main__': n = 5 c = 15 w = [5, 4, 7, 2, 6] v = [12, 3, 10, 3, 6] value = bag(n, c, w, v) # [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] # [0, 0, 0, 0, 0, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12] # [0, 0, 0, 0, 3, 12, 12, 12, 12, 15, 15, 15, 15, 15, 15, 15] # [0, 0, 0, 0, 3, 12, 12, 12, 12, 15, 15, 15, 22, 22, 22, 22] # [0, 0, 3, 3, 3, 12, 12, 15, 15, 15, 15, 18, 22, 22, 25, 25] # [0, 0, 3, 3, 3, 12, 12, 15, 15, 15, 15, 18, 22, 22, 25, 25] show(n, c, w, value) # 最大价值为: 25 # 背包中所装物品为: # 第 1 个,第 3 个,第 4 个, print('\n空间复杂度优化为N(c)结果:', bag1(n, c, w, v)) # 空间复杂度优化为N(c)结果: [0, 0, 3, 3, 3, 12, 12, 15, 15, 15, 15, 18, 22, 22, 25, 25]

64. 最小路径和

https://leetcode-cn.com/problems/minimum-path-sum/solution/zi-di-xiang-shang-he-zi-ding-xiang-xia-by-powcai/

问题描述： 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明： 每次只能向下或者向右移动一步。

示例:

输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。

解题思路： 动态规划,用dp[i][j]表示到i,j的最小路径和.

动态方程: dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

注意这里的第一行,和第一列要单独考虑,

还有可以直接在grid上操作,优化空间! 代码实现：

class Solution: def minPathSum(self, grid: List[List[int]]) -> int: if not grid: return 0 row = len(grid) col = len(grid[0]) dp = [[0]*col for _ in range(row)] dp[0][0] = grid[0][0] # 第一行 for j in range(1, col): dp[0][j] = dp[0][j-1] + grid[0][j] # 第一列 for i in range(1, row): dp[i][0] = dp[i-1][0] + grid[i][0] for i in range(1, row): for j in range(1, col): dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] return dp[-1][-1]

72. 编辑距离

https://leetcode-cn.com/problems/edit-distance/ 问题描述： 给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符删除一个字符替换一个字符

示例 1:

输入: word1 = “horse”, word2 = “ros” 输出: 3 解释: horse -> rorse (将 ‘h’ 替换为 ‘r’) rorse -> rose (删除 ‘r’) rose -> ros (删除 ‘e’)

示例 2:

输入: word1 = “intention”, word2 = “execution” 输出: 5 解释: intention -> inention (删除 ‘t’) inention -> enention (将 ‘i’ 替换为 ‘e’) enention -> exention (将 ‘n’ 替换为 ‘x’) exention -> exection (将 ‘n’ 替换为 ‘c’) exection -> execution (插入 ‘u’)

解题思路：

step1: 状态 首先只定义一维 DP[i] 不能有效简化问题的处理 使用 二维 DP[i][j]，表示 word1 的 i 个字母 与 word2 的 第 j 个字母 相同 需要的操作步骤数 将最对 word1 处理 转化为 对 word1 和 word2 均处理 word1 插入一个字符 DP[i-1][j] + 1 -> DP[i][j] word1 删除一个字符 = word2 插入一个字符 DP[i][j-1] + 1 -> DP[i][j] word1 替换一个字符 = word1 word2 都替换一个字符 DP[i-1][j-1] + 1 -> DP[i][j]

step2: 动态方程 DP[i][j] A、 word1 的 i 个字母 与 word2 的 第 j 个字母 相同 DP[i][j] = DP[i-1][j-1] #不操作 B、不相同,需要进行 插入 删除 或者 替换操作 DP[i][j] = min(DP[i-1][j] + 1,DP[i][j-1] + 1,DP[i-1][j-1]+1) 代码实现：

class Solution: def minDistance(self, word1: str, word2: str) -> int: len1 = len(word1) len2 = len(word2) M = [[j for i in range(len1+1)]for j in range(len2+1)] M[0] = [i for i in range(len1+1)] R = len(M) C = len(M[0]) for c in range(1,C): for r in range(1,R): if word1[c-1] == word2[r-1]: M[r][c] = M[r-1][c-1] else: M[r][c] = min(M[r-1][c], M[r][c-1], M[r-1][c-1])+1 return M[-1][-1]

编程实现查找两个字符串的最长公共子序列

解题思路： 序列a共有m个元素，序列b共有n个元素，如果a[m-1]==b[n-1]，那么a[:m]和b[:n]的最长公共子序列长度就是a[:m-1]和b[:n-1]的最长公共子序列长度+1；如果a[m-1]!=b[n-1]，那么a[:m]和b[:n]的最长公共子序列长度就是MAX（a[:m-1]和b[:n]的最长公共子序列长度，a[:m]和b[:n-1]的最长公共子序列长度）。 其中c[i,j]表示：(a1,a2…ai) 和 (b1,b2…bj) 的最长公共子序列的长度。

图示： 代码实现：

def lcs(a,b): lena=len(a) lenb=len(b) c=[[0 for i in range(lenb+1)] for j in range(lena+1)] flag=[[0 for i in range(lenb+1)] for j in range(lena+1)] for i in range(lena): for j in range(lenb): if a[i]==b[j]: c[i+1][j+1]=c[i][j]+1 flag[i+1][j+1]='ok' elif c[i+1][j]>c[i][j+1]: c[i+1][j+1]=c[i+1][j] flag[i+1][j+1]='left' else: c[i+1][j+1]=c[i][j+1] flag[i+1][j+1]='up' return c,flag def printLcs(flag,a,i,j): if i==0 or j==0: return if flag[i][j]=='ok': printLcs(flag,a,i-1,j-1) print(a[i-1],end='') elif flag[i][j]=='left': printLcs(flag,a,i,j-1) else: printLcs(flag,a,i-1,j) a='ABCBDAB' b='BDCABA' c,flag=lcs(a,b) for i in c: print(i) print('') for j in flag: print(j) print('') printLcs(flag,a,len(a),len(b)) print('')

673. 最长递增子序列的个数（编程实现一个数据序列的最长递增子序列）

https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence/ 问题描述： 给定一个未排序的整数数组，找到最长递增子序列的个数。

示例 1:

输入: [1,3,5,4,7] 输出: 2 解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

示例 2:

输入: [2,2,2,2,2] 输出: 5 解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。 注意: 给定的数组长度不超过 2000 并且结果一定是32位有符号整数。

解题思路： 思想基本和求最长递增子序列的长度类似。不同之处在于要记录每个位置 i 放数字num时的递增序列个数 dic[i][num]。 当数字 newnum 放在 i+1 位置时，dic[i+1][newnum] 的值为 dic[i] 中小于newnum 的num 的序列个数之和。

代码实现：

class Solution: def findNumberOfLIS(self, nums: List[int]) -> int: if not nums: return 0 l = len(nums) dq = list() totals = list() for num in nums: index = len(dq)-1 if not dq or num >dq[-1]: dq.append(num) totals.append(collections.defaultdict(int)) else: while index >= 0 and dq[index]>= num: index -= 1 dq[index+1] = num if not index+1: totals[index+1][num] +=1 else: totals[index+1][num] += sum([val for key,val in totals[index].items() if key <num ]) return sum(totals[-1].values())

五、练习

实战递归：

17. 电话号码的字母组合

https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/ 问题描述： 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

输入：“23” 输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

说明: 尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

代码实现：

class Solution: def letterCombinations(self, digits: str) -> List[str]: if not digits: return [] map = {'2': ['a', 'b', 'c'], '3': ['d', 'e', 'f'], '4': ['g', 'h', 'i'], '5': ['j', 'k', 'l'], '6': ['m', 'n', 'o'], '7': ['p', 'q', 'r', 's'], '8': ['t', 'u', 'v'], '9': ['w', 'x', 'y', 'z']} ret= [] def gen(index, path=''): if index == len(digits): return ret.append(path) for i in map[digits[index]]: gen(index + 1, path + i) gen(0) return ret

46. 全排列

问题描述： 给定一个没有重复数字的序列，返回其所有可能的全排列。 https://leetcode-cn.com/problems/permutations/ 示例:

输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

解题思路（官方）： 回溯法 是一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认不是一个解的话（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化抛弃该解，即回溯并且再次尝试。

这里有一个回溯函数，使用第一个整数的索引作为参数 backtrack(first)。

如果第一个整数有索引 n，意味着当前排列已完成。 遍历索引 first 到索引 n - 1 的所有整数。Iterate over the integers from index first to index n - 1. 在排列中放置第 i 个整数， 即 swap(nums[first], nums[i]). 继续生成从第 i 个整数开始的所有排列: backtrack(first + 1). 现在回溯，即通过 swap(nums[first], nums[i]) 还原.

代码实现：

class Solution: def permute(self, nums: List[int]) -> List[List[int]]: def backtrack(first = 0): # if all integers are used up if first == n: output.append(nums[:]) for i in range(first, n): # place i-th integer first # in the current permutation nums[first], nums[i] = nums[i], nums[first] # use next integers to complete the permutations backtrack(first + 1) # backtrack nums[first], nums[i] = nums[i], nums[first] n = len(nums) output = [] backtrack() return output

实战DP（动态规划）

132. 分割回文串 II

https://leetcode-cn.com/problems/palindrome-partitioning-ii/comments/ 问题描述： 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回符合要求的最少分割次数。

示例:

输入: “aab” 输出: 1 解释: 进行一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子串。

代码实现：

class Solution: def minCut(self, s: str) -> int: if not s or s == s[::-1]: return 0 n = len(s) for i in range(1, n): if s[:i] == s[:i][::-1] and s[i:] == s[i:][::-1]: return 1 dp = list(range(-1, n)) for i in range(n): for k in range(0, min(n - i, i + 1)): if s[i + k] != s[i - k]: break dp[i + k + 1] = min(dp[i + k + 1], dp[i - k] + 1) for k in range(1, min(n - i, i + 2)): if s[i + k] != s[i - k + 1]: break dp[i + k + 1] = min(dp[i + k + 1], dp[i - k + 1] + 1) return dp[n]

10. 正则表达式匹配

https://leetcode-cn.com/problems/regular-expression-matching/ 问题描述： 给定一个字符串 (s) 和一个字符模式 §。实现支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符。 ‘*’ 匹配零个或多个前面的元素。

匹配应该覆盖整个字符串 (s) ，而不是部分字符串。

说明:

s 可能为空，且只包含从 a-z 的小写字母。p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

示例 1:

输入: s = “aa” p = “a” 输出: false 解释: “a” 无法匹配 “aa” 整个字符串。

示例 2:

输入: s = “aa” p = “a*” 输出: true 解释: ‘*’ 代表可匹配零个或多个前面的元素, 即可以匹配 ‘a’ 。因此, 重复 ‘a’ 一次, 字符串可变为 “aa”。

示例 3:

输入: s = “ab” p = “." 输出: true 解释: ".” 表示可匹配零个或多个(’*’)任意字符(’.’)。

示例 4:

输入: s = “aab” p = “cab” 输出: true 解释: ‘c’ 可以不被重复, ‘a’ 可以被重复一次。因此可以匹配字符串 “aab”。

示例 5:

输入: s = “mississippi” p = “misisp*.” 输出: false

解题思路： 动态规划：

p[j] == s[i]:dp[i][j] = dp[i-1][j-1]p[j] == “.”:dp[i][j] = dp[i-1][j-1]p[j] =="*": 3.1 p[j-1] != s[i]:dp[i][j] = dp[i][j-2] 3.2 p[i-1] == s[i] or p[i-1] == “.”: dp[i][j] = dp[i-1][j] // 多个a的情况 or dp[i][j] = dp[i][j-1] // 单个a的情况 or dp[i][j] = dp[i][j-2] // 没有a的情况

代码实现

class Solution: def isMatch(self, s: str, p: str) -> bool: #if not s or not p: #return False s_len = len(s) p_len = len(p) dp = [[False] * (p_len + 1) for _ in range(s_len + 1)] #print(dp) dp[0][0] = True for i in range(p_len): if p[i] == "*" and dp[0][i - 1]: dp[0][i + 1] = True #print(dp) for i in range(s_len): for j in range(p_len): if p[j] == s[i] or p[j] == ".": dp[i + 1][j + 1] = dp[i][j] elif p[j] == "*": if p[j - 1] != s[i]: dp[i + 1][j + 1] = dp[i + 1][j - 1] if p[j-1] == s[i] or p[j-1] == ".": dp[i+1][j+1] = (dp[i][j+1] or dp[i+1][j] or dp[i+1][j-1]) #print(dp) return dp[-1][-1]

322. 零钱兑换

https://leetcode-cn.com/problems/coin-change/ 问题描述： 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:

输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1

示例 2:

输入: coins = [2], amount = 3 输出: -1

说明: 你可以认为每种硬币的数量是无限的。

代码实现

class Solution: def coinChange(self, coins: 'List[int]', amount: 'int') -> 'int': dp = [float("inf")] * (amount+1) dp[0] = 0 for i in range(1,amount+1): for coin in coins: if i - coin>= 0: dp[i] = min(dp[i],dp[i-coin]+1) # print(dp) return dp[-1] if dp[-1]!= float("inf") else -1

121. 买卖股票的最佳时机

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/ 问题描述： 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

解题思路： 最大利润=max{前一天最大利润, 今天的价格 - 之前最低价格}

代码实现：

class Solution: def maxProfit(self, prices: List[int]) -> int: if (len(prices)<=1): return 0 min_p=prices[0] max_p=0 for i in range(len(prices)): min_p= min(min_p,prices[i]) max_p= max(max_p,prices[i]-min_p) return max_p

152. 乘积最大子序列

https://leetcode-cn.com/problems/maximum-product-subarray/ 问题描述： 给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

示例 1:

输入: [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

解题思路： 类似于动态规划思想，一次遍历，每一步的中间变量表示当前位置的最大正值和负值，对长度大于1的结果必定是大于0的，所有当当前位置连续乘积最大值小于0或最小值大于0时都令成0即可，比较res和当前最大正值即可。

代码实现：

class Solution: def maxProduct(self, nums: List[int]) -> int: res = nums[0] mid = [0,0] if nums[0] >= 0: mid = [0,nums[0]] else: mid = [nums[0],0] for i in range(1,len(nums)): if nums[i] >= 0: mid[1] = max(nums[i],nums[i]*mid[1]) mid[0] = mid[0]*nums[i] else: mid[0],mid[1] = min(nums[i],nums[i]*mid[1]), nums[i]*mid[0] res = max(res,mid[1]) return res

120. 三角形最小路径和

https://leetcode-cn.com/problems/maximum-product-subarray/ 问题描述： 给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

[ [2], [3,4], [6,5,7], [4,1,8,3] ]

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。 说明： 如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

代码实现：

class Solution: def minimumTotal(self, triangle: List[List[int]]) -> int: if len(triangle) == 0: return 0 row = len(triangle) - 2 for row in range(row, -1, -1): for col in range(len(triangle[row])): triangle[row][col] += min(triangle[row+1][col],triangle[row+1][col+1]) return triangle[0][0]