Python版_Leetcode_hot100系列(16)--多维动态规划

class Solution:    def uniquePaths(self, m: int, n: int) -> int:        """        动态规划解法 - 时间复杂度O(m×n)，空间复杂度O(n)        """        # 使用一维数组优化空间        dp = [1] * n        for i in range(1, m):            for j in range(1, n):                dp[j] = dp[j] + dp[j-1]        return dp[-1]

示例：m = 3, n = 7初始：dp = [1, 1, 1, 1, 1, 1, 1]第1行（i = 0）：保持不变  dp = [1, 1, 1, 1, 1, 1, 1]第2行（i = 1）：  j = 1: dp[1] = dp[1] + dp[0] = 1 + 1 = 2  j = 2: dp[2] = dp[2] + dp[1] = 1 + 2 = 3  j = 3: dp[3] = dp[3] + dp[2] = 1 + 3 = 4  j = 4: dp[4] = dp[4] + dp[3] = 1 + 4 = 5  j = 5: dp[5] = dp[5] + dp[4] = 1 + 5 = 6  j = 6: dp[6] = dp[6] + dp[5] = 1 + 6 = 7  dp = [1, 2, 3, 4, 5, 6, 7]第3行（i = 2）：  j = 1: dp[1] = dp[1] + dp[0] = 2 + 1 = 3  j = 2: dp[2] = dp[2] + dp[1] = 3 + 3 = 6  j = 3: dp[3] = dp[3] + dp[2] = 4 + 6 = 10  j = 4: dp[4] = dp[4] + dp[3] = 5 + 10 = 15  j = 5: dp[5] = dp[5] + dp[4] = 6 + 15 = 21  j = 6: dp[6] = dp[6] + dp[5] = 7 + 21 = 28  dp = [1, 3, 6, 10, 15, 21, 28]结束：return dp[-1] = 28 ✅

class Solution:    def minPathSum(self, grid: List[List[int]]) -> int:        """        动态规划解法 - 时间复杂度O(m×n)，空间复杂度O(n)        """        if not grid or not grid[0]:            return 0        m, n = len(grid), len(grid[0])        dp = [0] * n        for i in range(m):            for j in range(n):                if i == 0 and j == 0:                    dp[j] = grid[i][j]                elif i == 0:                    dp[j] = dp[j-1] + grid[i][j]                elif j == 0:                    dp[j] = dp[j] + grid[i][j]                else:                    dp[j] = min(dp[j], dp[j-1]) + grid[i][j]        return dp[-1]

示例：grid = [  [1, 3, 1],  [1, 5, 1],  [4, 2, 1]]初始：dp = [0, 0, 0]第1行（i = 0）：  j = 0: dp[0] = grid[0][0] = 1  j = 1: dp[1] = dp[0] + grid[0][1] = 1 + 3 = 4  j = 2: dp[2] = dp[1] + grid[0][2] = 4 + 1 = 5  dp = [1, 4, 5]第2行（i = 1）：  j = 0: dp[0] = dp[0] + grid[1][0] = 1 + 1 = 2  j = 1: dp[1] = min(dp[1], dp[0]) + grid[1][1] = min(4, 2) + 5 = 7  j = 2: dp[2] = min(dp[2], dp[1]) + grid[1][2] = min(5, 7) + 1 = 6  dp = [2, 7, 6]第3行（i = 2）：  j = 0: dp[0] = dp[0] + grid[2][0] = 2 + 4 = 6  j = 1: dp[1] = min(dp[1], dp[0]) + grid[2][1] = min(7, 6) + 2 = 8  j = 2: dp[2] = min(dp[2], dp[1]) + grid[2][2] = min(6, 8) + 1 = 7  dp = [6, 8, 7]结束：return dp[-1] = 7 ✅验证：最小路径为 1→3→1→1→1，和为7

class Solution:    def longestPalindrome(self, s: str) -> str:        """        中心扩展法 - 时间复杂度O(n²)，空间复杂度O(1)        """        if not s:            return ""        start = 0        max_length = 1        for i in range(len(s)):            # 奇数长度回文（中心为单个字符）            self.expandAroundCenter(s, i, i, start, max_length)            # 偶数长度回文（中心为字符间隙）            self.expandAroundCenter(s, i, i + 1, start, max_length)        return s[start:start + max_length]    def expandAroundCenter(self, s: str, left: int, right: int, start: int, max_length: int):        while left >= 0 and right < len(s) and s[left] == s[right]:            current_length = right - left + 1            if current_length > max_length:                max_length = current_length                start = left            left -= 1            right += 1        return start, max_length

示例：s = "babad"初始：start = 0, max_length = 1第1步：i = 0  奇数中心 (0, 0):    left = 0, right = 0, s[0] = 'b' = s[0] = 'b'    current_length = 1, max_length = 1, start = 0    left = -1, right = 1, 停止  偶数中心 (0, 1):    left = 0, right = 1, s[0] = 'b' ≠ s[1] = 'a'    停止第2步：i = 1  奇数中心 (1, 1):    left = 1, right = 1, s[1] = 'a' = s[1] = 'a'    current_length = 1, max_length = 1, start = 0    left = 0, right = 2, s[0] = 'b' ≠ s[2] = 'b'    停止  偶数中心 (1, 2):    left = 1, right = 2, s[1] = 'a' ≠ s[2] = 'b'    停止第3步：i = 2  奇数中心 (2, 2):    left = 2, right = 2, s[2] = 'b' = s[2] = 'b'    current_length = 1, max_length = 1, start = 0    left = 1, right = 3, s[1] = 'a' = s[3] = 'a'    current_length = 3, max_length = 3, start = 1    left = 0, right = 4, s[0] = 'b' ≠ s[4] = 'd'    停止  偶数中心 (2, 3):    left = 2, right = 3, s[2] = 'b' ≠ s[3] = 'a'    停止第4步：i = 3  奇数中心 (3, 3):    left = 3, right = 3, s[3] = 'a' = s[3] = 'a'    current_length = 1, max_length = 3, start = 1    left = 2, right = 4, s[2] = 'b' ≠ s[4] = 'd'    停止  偶数中心 (3, 4):    left = 3, right = 4, s[3] = 'a' ≠ s[4] = 'd'    停止第5步：i = 4  奇数中心 (4, 4):    left = 4, right = 4, s[4] = 'd' = s[4] = 'd'  current_length = 1, max_length = 3, start = 1left = 3, right = 5, 停止偶数中心 (4, 5):left = 4, right = 5, 停止结束：return s[1:1+3] = "bab" ✅验证：最长回文子串为 "bab" 或 "aba"，长度为3

class Solution:    def longestCommonSubsequence(self, text1: str, text2: str) -> int:        """        动态规划解法 - 时间复杂度O(m×n)，空间复杂度O(n)        """        m, n = len(text1), len(text2)        # 使用一维数组优化空间        dp = [0] * (n + 1)        for i in range(1, m + 1):            prev = 0  # 保存dp[i-1][j-1]的值            for j in range(1, n + 1):                temp = dp[j]  # 保存当前的dp[i-1][j]                if text1[i-1] == text2[j-1]:                    dp[j] = prev + 1                else:                    dp[j] = max(dp[j], dp[j-1])                prev = temp        return dp[n]

示例：text1 = "abcde", text2 = "ace"初始：m = 5, n = 3, dp = [0, 0, 0, 0]第1行（i = 1, text1[0] = 'a'）：prev = 0j = 1: text1[0] = 'a' == text2[0] = 'a'temp = dp[1] = 0dp[1] = prev + 1 = 1prev = temp = 0j = 2: text1[0] = 'a' != text2[1] = 'c'temp = dp[2] = 0dp[2] = max(dp[2], dp[1]) = max(0, 1) = 1prev = temp = 0j = 3: text1[0] = 'a' != text2[2] = 'e'temp = dp[3] = 0dp[3] = max(dp[3], dp[2]) = max(0, 1) = 1prev = temp = 0dp = [0, 1, 1, 1]第2行（i = 2, text1[1] = 'b'）：prev = 0j = 1: text1[1] = 'b' != text2[0] = 'a'temp = dp[1] = 1dp[1] = max(dp[1], dp[0]) = max(1, 0) = 1prev = temp = 1j = 2: text1[1] = 'b' != text2[1] = 'c'temp = dp[2] = 1dp[2] = max(dp[2], dp[1]) = max(1, 1) = 1prev = temp = 1j = 3: text1[1] = 'b' != text2[2] = 'e'temp = dp[3] = 1dp[3] = max(dp[3], dp[2]) = max(1, 1) = 1prev = temp = 1dp = [0, 1, 1, 1]第3行（i = 3, text1[2] = 'c'）：prev = 0j = 1: text1[2] = 'c' != text2[0] = 'a'temp = dp[1] = 1dp[1] = max(dp[1], dp[0]) = max(1, 0) = 1prev = temp = 1j = 2: text1[2] = 'c' == text2[1] = 'c'temp = dp[2] = 1dp[2] = prev + 1 = 2prev = temp = 1j = 3: text1[2] = 'c' != text2[2] = 'e'temp = dp[3] = 1dp[3] = max(dp[3], dp[2]) = max(1, 2) = 2prev = temp = 1dp = [0, 1, 2, 2]第4行（i = 4, text1[3] = 'd'）：prev = 0j = 1: text1[3] = 'd' != text2[0] = 'a'temp = dp[1] = 1dp[1] = max(dp[1], dp[0]) = max(1, 0) = 1prev = temp = 1j = 2: text1[3] = 'd' != text2[1] = 'c'temp = dp[2] = 2dp[2] = max(dp[2], dp[1]) = max(2, 1) = 2prev = temp = 2j = 3: text1[3] = 'd' != text2[2] = 'e'temp = dp[3] = 2dp[3] = max(dp[3], dp[2]) = max(2, 2) = 2prev = temp = 2dp = [0, 1, 2, 2]第5行（i = 5, text1[4] = 'e'）：prev = 0j = 1: text1[4] = 'e' != text2[0] = 'a'temp = dp[1] = 1dp[1] = max(dp[1], dp[0]) = max(1, 0) = 1prev = temp = 1j = 2: text1[4] = 'e' != text2[1] = 'c'temp = dp[2] = 2dp[2] = max(dp[2], dp[1]) = max(2, 1) = 2prev = temp = 2j = 3: text1[4] = 'e' == text2[2] = 'e'temp = dp[3] = 2dp[3] = prev + 1 = 3prev = temp = 2dp = [0, 1, 2, 3]结束：return dp[3] = 3 ✅验证：最长公共子序列为 "ace"，长度为3

class Solution:    def minDistance(self, word1: str, word2: str) -> int:        """        动态规划解法 - 时间复杂度O(m×n)，空间复杂度O(m×n)        """        m, n = len(word1), len(word2)        # 创建dp数组        dp = [[0] * (n + 1) for _ in range(m + 1)]        # 初始化边界条件        for i in range(m + 1):            dp[i][0] = i  # 删除i个字符        for j in range(n + 1):            dp[0][j] = j  # 插入j个字符        # 填充dp数组        for i in range(1, m + 1):            for j in range(1, n + 1):                if word1[i-1] == word2[j-1]:                    dp[i][j] = dp[i-1][j-1]                else:                    dp[i][j] = min(                        dp[i-1][j] + 1,    # 删除                        dp[i][j-1] + 1,    # 插入                        dp[i-1][j-1] + 1   # 替换                    )        return dp[m][n]

示例：word1 = "horse", word2 = "ros"初始：m = 5, n = 3dp = [  [0, 1, 2, 3],  [1, 0, 0, 0],  [2, 0, 0, 0],  [3, 0, 0, 0],  [4, 0, 0, 0],  [5, 0, 0, 0]]第1行（i = 1, word1[0] = 'h'）：  j = 1: word1[0] = 'h' != word2[0] = 'r'    dp[1][1] = min(dp[0][1] + 1, dp[1][0] + 1, dp[0][0] + 1)       = min(1 + 1, 1 + 1, 0 + 1) = 1  j = 2: word1[0] = 'h' != word2[1] = 'o'    dp[1][2] = min(dp[0][2] + 1, dp[1][1] + 1, dp[0][1] + 1)       = min(2 + 1, 1 + 1, 1 + 1) = 2  j = 3: word1[0] = 'h' != word2[2] = 's'    dp[1][3] = min(dp[0][3] + 1, dp[1][2] + 1, dp[0][2] + 1)       = min(3 + 1, 2 + 1, 2 + 1) = 3第2行（i = 2, word1[1] = 'o'）：  j = 1: word1[1] = 'o' != word2[0] = 'r'    dp[2][1] = min(dp[1][1] + 1, dp[2][0] + 1, dp[1][0] + 1)       = min(1 + 1, 2 + 1, 1 + 1) = 2  j = 2: word1[1] = 'o' == word2[1] = 'o'    dp[2][2] = dp[1][1] = 1  j = 3: word1[1] = 'o' != word2[2] = 's'    dp[2][3] = min(dp[1][3] + 1, dp[2][2] + 1, dp[1][2] + 1)       = min(3 + 1, 1 + 1, 2 + 1) = 2第3行（i = 3, word1[2] = 'r'）：  j = 1: word1[2] = 'r' == word2[0] = 'r'    dp[3][1] = dp[2][0] = 2  j = 2: word1[2] = 'r' != word2[1] = 'o'    dp[3][2] = min(dp[2][2] + 1, dp[3][1] + 1, dp[2][1] + 1)       = min(1 + 1, 2 + 1, 2 + 1) = 2  j = 3: word1[2] = 'r' != word2[2] = 's'    dp[3][3] = min(dp[2][3] + 1, dp[3][2] + 1, dp[2][2] + 1)       = min(2 + 1, 2 + 1, 1 + 1) = 2第4行（i = 4, word1[3] = 's'）：  j = 1: word1[3] = 's' != word2[0] = 'r'    dp[4][1] = min(dp[3][1] + 1, dp[4][0] + 1, dp[3][0] + 1)       = min(2 + 1, 4 + 1, 3 + 1) = 3  j = 2: word1[3] = 's' != word2[1] = 'o'    dp[4][2] = min(dp[3][2] + 1, dp[4][1] + 1, dp[3][1] + 1)       = min(2 + 1, 3 + 1, 2 + 1) = 3  j = 3: word1[3] = 's' == word2[2] = 's'    dp[4][3] = dp[3][2] = 2第5行（i = 5, word1[4] = 'e'）：  j = 1: word1[4] = 'e' != word2[0] = 'r'    dp[5][1] = min(dp[4][1] + 1, dp[5][0] + 1, dp[4][0] + 1)       = min(3 + 1, 5 + 1, 4 + 1) = 4  j = 2: word1[4] = 'e' != word2[1] = 'o'    dp[5][2] = min(dp[4][2] + 1, dp[5][1] + 1, dp[4][1] + 1)       = min(3 + 1, 4 + 1, 3 + 1) = 4  j = 3: word1[4] = 'e' != word2[2] = 's'    dp[5][3] = min(dp[4][3] + 1, dp[5][2] + 1, dp[4][2] + 1)       = min(2 + 1, 4 + 1, 3 + 1) = 3结束：return dp[5][3] = 3 ✅验证：horse → rse → rose → ros，共3步操作