多维动态规划91-95

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,nlen(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): maxlen0 start0 nlen(s) dp[[False]*n for i in range(n)] for i in range(n): maxlen1 dp[i][i]True for length in range(2, n1): for i in range(n - length 1): j i length - 1 if s[i] s[j] and (length 2 or dp[i1][j-1]): dp[i][j] True start i maxlen length return s[start:startmaxlen]94. 最长公共子序列class Solution(object): def longestCommonSubsequence(self, text1, text2): m,nlen(text1),len(text2) dp[[0]*(n1) for _ in range(m1)] for i in range(1,m1): for j in range(1,n1): 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)): leftnums[i-1] if i0 else 1001 rightnums[i1] if ilen(nums)-1 else 1001 ans[i%2]max(0, nums[i] - min(left, right) 1) return min(ans)