经典题目（4）：矩阵的最小路径和；最长回文子串

BM68 矩阵的最小路径和描述给定一个 n * m 的矩阵 a从左上角开始每次只能向右或者向下走最后到达右下角的位置路径上所有的数字累加起来就是路径和输出所有的路径中最小的路径和。数据范围: 1≤n,m≤500矩阵中任意值都满足 0≤ai,j≤100要求时间复杂度 O(nm)代码class Solution: def minPathSum(self , matrix: List[List[int]]) - int: # write code here mlen(matrix) nlen(matrix[0]) dp[[0]*n for _ in range(m)] dp[0][0]matrix[0][0] for i in range(1,m): dp[i][0]dp[i-1][0]matrix[i][0] for i in range(1,n): dp[0][i]dp[0][i-1]matrix[0][i] for i in range(1,m): for j in range(1,n): dp[i][j]min(dp[i-1][j],dp[i][j-1])matrix[i][j] return dp[-1][-1]BM73最长回文子串描述对于长度为n的一个字符串A仅包含数字大小写英文字母请设计一个高效算法计算其中最长回文子串的长度。数据范围 1≤n≤10001≤n≤1000要求空间复杂度 O(1)时间复杂度 O(n2)进阶: 空间复杂度 O(n)时间复杂度 O(n)方法分三种情况首先right-left1其次right-left2最后一种 dp[left1][right-1] 为true代码class Solution: def getLongestPalindrome(self , A: str) - int: # write code here nlen(A) dp[[0]*n for _ in range(n)] for right in range(1,n): for left in range(0,right): if right-left1: if A[right]A[left]: dp[left][right]True if right-left2: if A[right]A[left]: dp[left][right]True else: if dp[left1][right-1]True: if A[right]A[left]: dp[left][right]True result1 for right in range(1,n): for left in range(0,right): if dp[left][right]True: resultmax(result,right-left1) return result