HOT100（九）多维动态规划

一、多维动态规划

1、不同路径

①常规思路

维护一个二维数组f，f[i][j]表示从起点到(i,j)的路径数。

已知初始化f[0][0]=1，即机器人在起点的路径是1；机器人到达第一列f[:][0]只能从上方这一条路走下来，因此第一列的每个元素都为1；机器人到达第一行f[0][:]只能从左方这一条路走下来，因此第一行的每个元素都为1。

状态转移公式：f[i][j]=f[i-1][j]+f[i][j-1]，这是因为机器人到达一个点（i,j），只能从上方和左方走过来，因此到达（i,j）的路径之和=到达（i-1,j）的路径总数+到达（i,j-1)的路径总数。

class Solution:def uniquePaths(self, m: int, n: int) -> int:f=[[1]*n for _ in range(m)]for i in range(1,m):for j in range(1,n):f[i][j]=f[i-1][j]+f[i][j-1]return f[m-1][n-1]

②优化空间复杂度

对于上面的二维状态数组而言，当我们遍历到第 i 行时，f[i][j] 的计算只依赖于当前 j 列（也就是 cur[j]，对应的是 f[i-1][j] 的值）和 j-1 列（也就是cur[j-1]，对应的是 f[i][j-1] 的值）

class Solution:def uniquePaths(self, m: int, n: int) -> int:cur=[1]*nfor i in range(1,m):for j in range(1,n):cur[j]+=cur[j-1]return cur[n-1]

2、 最小路径和

对于第一行来说，只能从左往右走；对于第一列来说，只能从上往下走。所以初始化grid[i][0]=grid[i-1][0]+grid[i][0]，grid[0][j]=grid[0][j-1]+grid[0][j]。

因为只能向下或向右到达某个位置，因此到达一个位置的最小路径和等于到达其上方位置的最小路径和加当前位置值和到达其左方位置的最小路径和加当前位置值中的最小值。

class Solution:def minPathSum(self, grid: List[List[int]]) -> int:if not grid or not grid[0]:return 0m,n=len(grid),len(grid[0])for i in range(1,m):grid[i][0]=grid[i-1][0]+grid[i][0]for j in range(1,n):grid[0][j]=grid[0][j-1]+grid[0][j]for i in range(1,m):for j in range(1,n):grid[i][j]=min(grid[i-1][j]+grid[i][j],grid[i][j-1]+grid[i][j])return grid[m-1][n-1]

3、最长回文子串

①动态规划

• 状态定义：使用一个二维数组 dp[i][j] 表示字符串从第 i 到第 j 的子串是否是回文串。如果是回文串，则 dp[i][j] = True，否则为 False。
• 状态转移方程：对于子串 s[i:j+1]，如果 s[i] == s[j]，并且内部的子串 s[i+1:j-1] 也是回文串（即 dp[i+1][j-1] = True），那么 dp[i][j] = True。
• 初始化：所有长度为 1 的子串显然是回文串，因此初始化时 dp[i][i] = True。
• 结果更新：在填充 dp 数组的同时，记录最长的回文子串的起始位置和长度。

时间复杂度和空间复杂度都是O(n²)。

class Solution:def longestPalindrome(self, s: str) -> str:if not s:return ""n=len(s)if n==1:return sdp=[[False]*n for _ in range(n)]for i in range(n):dp[i][i]=Truestart=0;max_len=1for j in range(1,n):for i in range(j):if s[i]==s[j]:if j==i+1:dp[i][j]=Trueelse:dp[i][j]=dp[i+1][j-1]if dp[i][j] and j-i+1>max_len:max_len=j-i+1start=ireturn s[start:start+max_len]

②中心扩展

基本思想是，对于每个字符（或字符之间的空隙）作为中心，向两边扩展，找到以该中心为轴对称的回文子串，并记录最长的回文子串。

• 中心的选择：回文的中心可以是一个字符（回文长度为奇数）或者两个字符之间的空隙（回文长度为偶数）。所以，对于一个长度为 n 的字符串，有 2n-1 个可能的中心（包括字符本身和字符之间的空隙）。

• 扩展过程：对于每个中心，从中心向两边扩展，检查字符是否相同，直到扩展不再满足回文条件为止。

• 记录结果：在每次扩展的过程中，记录下当前回文的长度，如果发现更长的回文子串，就更新结果。

class Solution:def longestPalindrome(self, s: str) -> str:if not s:return ""n=len(s)def expand(s,left,right):while left>=0 and right<len(s) and s[left]==s[right]:left-=1right+=1return right-left-1start=0;max_len=1for i in range(n):len1=expand(s,i,i)len2=expand(s,i,i+1)curr_max=max(len1,len2)if curr_max>max_len:max_len=curr_maxstart=i-(curr_max-1)//2return s[start:start+max_len]

4、最长公共子序列

维护一个状态数组f，f[i][j]表示text1的前i个元素 与 text2的前j个元素 的最长公共子序列。

若text1和text2当前元素相等，那么扩展最长公共子序列，表示为f[i][j]=f[i-1][j-1]+1。

若text1和text2当前元素不相等，那么当前最长公共子序列长度可表示为：f[i][j]=max(f[i][j-1],f[i-1][j])。

class Solution:def longestCommonSubsequence(self, text1: str, text2: str) -> int:n,m=len(text1),len(text2)f=[[0]*(m+1) for _ in range(n+1)]for i in range(1,n+1):for j in range(1,m+1):if text1[i-1]==text2[j-1]:f[i][j]=f[i-1][j-1]+1else:f[i][j]=max(f[i][j-1],f[i-1][j])return f[n][m]

5、编辑距离

维护一个二维数组f，f[i][j] 为将字符串 word1 的前 i 个字符转换为 word2 的前 j 个字符的最小编辑距离。

• 边界初始化：

  • 当 word1 的长度为 0 时（i=0），要将它转换为 word2 的前 j 个字符，最小操作数就是插入 j 个字符。因此，f[0][j] = j。
  • 同理，当 word2 的长度为 0 时（j=0），要将 word1 的前 i 个字符转换为空串，最小操作数就是删除 i 个字符。因此，f[i][0] = i。

• 状态转移方程： 对于任意 i 和 j，可以有以下三种操作来计算 f[i][j]：

  • 删除操作：从 word1[0:i] 删除一个字符，即从 f[i-1][j] + 1，表示删除了 word1[i-1]。
  • 插入操作：在 word1[0:i] 后插入一个字符，使其匹配 word2[j-1]，即从 f[i][j-1] + 1，表示插入了 word2[j-1]。
  • 替换操作：如果 word1[i-1] == word2[j-1]，则不需要操作，直接继承 f[i-1][j-1] 的值；如果 word1[i-1] != word2[j-1]，则需要一次替换操作，即 f[i-1][j-1] + 1。

class Solution:def minDistance(self, word1: str, word2: str) -> int:n,m=len(word1),len(word2)f=[[0]*(m+1) for _ in range(n+1)]for i in range(m+1):f[0][i]=ifor j in range(n+1):f[j][0]=jfor i in range(1,n+1):for j in range(1,m+1):f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1)if word1[i-1]==word2[j-1]:f[i][j]=min(f[i][j],f[i-1][j-1])else:f[i][j]=min(f[i][j],f[i-1][j-1]+1)return f[n][m]

二、技巧

1、只出现一次的数字

利用异或运算的性质，相同数字异或结果为0，0与任何数字异或结果仍为该数字。遍历数组，将所有数字进行异或运算。因为除了一个数字外，其他数字都成对出现，所以它们的异或结果会相互抵消，最后剩下的就是那个只出现一次的数字。

class Solution:def singleNumber(self, nums: List[int]) -> int:single=0for num in nums:single^=numreturn single

2、多数元素

①利用counter

class Solution:def majorityElement(self, nums: List[int]) -> int:counter=Counter(nums)half_len=len(nums)//2for num,count in counter.items():if count>half_len:return num

②利用排序

class Solution:def majorityElement(self, nums: List[int]) -> int:nums.sort()return nums[len(nums) // 2]

③Boyer-Moore 投票算法

多数元素，个数多于一半，所以最后的candidate一定是它。

class Solution:def majorityElement(self, nums: List[int]) -> int:count=0candidate=Nonefor num in nums:if count==0:candidate=numcount+=(1 if num==candidate else -1)return candidate

3、颜色分类

用快排去解决。

class Solution:def sortColors(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""def quicksort(nums,left,right):if left>=right:returnmid=(left+right)//2pivot=nums[mid]i=left-1;j=right+1while i<j:while True:i+=1if nums[i]>=pivot:breakwhile True:j-=1if nums[j]<=pivot:breakif i<j:nums[i],nums[j]=nums[j],nums[i]quicksort(nums,left,j)quicksort(nums,j+1,right)quicksort(nums,0,len(nums)-1)return nums

4、下一个排列

• 从右往左找到第一个位置 i，满足 nums[i] < nums[i + 1]：该位置 i 是需要调整的地方，表示从这个位置开始的子序列是降序排列的，因此它是字典序中最大的排列。

• 如果 i 找不到（说明整个数组是降序排列的），直接将整个数组反转：这意味着当前排列已经是字典序中最大的，反转后得到字典序最小的排列。

• 找到 i 之后，从右往左找到第一个位置 j，满足 nums[j] > nums[i]：nums[j] 是比 nums[i] 大的最小值，交换 nums[i] 和 nums[j]。

• 交换后，将 i 后面的子序列进行反转：因为交换后，i 后面的序列仍然是降序的，反转后能得到该部分的最小排列，从而得到整体的字典序的下一个排列。

class Solution:def nextPermutation(self, nums: List[int]) -> None:i=len(nums)-2while i>=0 and nums[i]>=nums[i+1]:i-=1if i>=0:j=len(nums)-1while j>=0 and nums[i]>=nums[j]:j-=1nums[i],nums[j]=nums[j],nums[i]left,right=i+1,len(nums)-1while left<right:nums[left],nums[right]=nums[right],nums[left]left+=1right-=1

5、寻找重复数

• 使用快慢指针，初始时两个指针都指向数组的第一个元素：慢指针每次走一步，快指针每次走两步。当快指针和慢指针相遇时，说明存在一个环（即重复数字）。
• 为了找到环的入口（即重复的数字），将一个指针重新指向数组的第一个元素，另一个指针留在相遇的地方。
• 两个指针每次都走一步，当它们再次相遇时，相遇点就是环的入口（即重复的数字）。

class Solution:def findDuplicate(self, nums: List[int]) -> int:slow=0;fast=0while True:slow=nums[slow]fast=nums[nums[fast]]if slow==fast:breakslow=0while slow!=fast:slow=nums[slow]fast=nums[fast]return slow