91. 不同路径
class Solution(object): def uniquePaths(self, m, n): dp=[[0]*n for _ in range(m)] for i in range(m): dp[i][0]=1 for j in range(n): dp[0][j]=1 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[m-1][n-1]
92. 最小路径和
class Solution(object): def minPathSum(self, grid): m,n=len(grid),len(grid[0]) dp=[[0]*n for _ in range(m)] dp[0][0]=grid[0][0] for i in range(1,m): dp[i][0]=grid[i][0]+dp[i-1][0] for j in range(1,n): dp[0][j]=grid[0][j]+dp[0][j-1] for i in range(1,m): for j in range(1,n): dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j] return dp[m-1][n-1]
93. 最长回文子串
class Solution(object): def longestPalindrome(self, s): maxlen=0 start=0 n=len(s) dp=[[False]*n for i in range(n)] for i in range(n): maxlen=1 dp[i][i]=True for length in range(2, n+1): for i in range(n - length + 1): j = i + length - 1 if s[i] == s[j] and (length == 2 or dp[i+1][j-1]): dp[i][j] = True start = i maxlen = length return s[start:start+maxlen]
94. 最长公共子序列
class Solution(object): def longestCommonSubsequence(self, text1, text2): m,n=len(text1),len(text2) dp=[[0]*(n+1) for _ in range(m+1)] for i in range(1,m+1): for j in range(1,n+1): if text1[i-1]==text2[j-1]: dp[i][j]=dp[i-1][j-1]+1 else: dp[i][j]=max(dp[i-1][j],dp[i][j-1]) return dp[m][n]
95. 编辑距离
class Solution(object): def movesToMakeZigzag(self, nums): ans=[0,0] for i in range(len(nums)): left=nums[i-1] if i>0 else 1001 right=nums[i+1] if i<len(nums)-1 else 1001 ans[i%2]+=max(0, nums[i] - min(left, right) + 1) return min(ans)
