多维动态规划（Multidimensional Dynamic Programming，简称MDP）是动态规划的一种扩展形式，它用于解决具有多个决策变量的优化问题。在传统的动态规划中，问题通常被描述为单变量或双变量问题，而多维动态规划则可以处理多个决策变量
摘要：多维动态规划 (1) 不同路径 """ 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一
多维动态规划
(1) 不同路径
"""
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？
"""
dp = [[1] * n for _ in range(m)]
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]
(2) 最小路径和
"""
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。
"""
m = len(grid)
n = len(grid[0])
dp = grid.copy()
for i in range(1, m):
dp[i][0] = dp[i-1][0]+grid[i][0]
for j in range(1, n):
dp[0][j] = dp[0][j-1]+grid[0][j]
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]
(3) 最长回文子串
"""
给你一个字符串 s，找到 s 中最长的回文子串。
"""
n = len(s)
res_left = res_right = 0
# 奇回文串
for i in range(n):
l = r = i
while l >= 0 and r < n and s[l] == s[r]:
l -= 1
r += 1
if r-l-1 > res_right-res_left:
res_left, res_right = l+1, r
# 偶回文串
for i in range(n-1):
l, r = i, i+1
while l >= 0 and r < n and s[l] == s[r]:
l -= 1
r += 1
if r-l-1 > res_right-res_left:
res_left, res_right = l+1, r
return s[res_left:res_right]
(4) 最长公共子序列
"""
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0。例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
"""
m = len(text1)
n = 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]
(5) 编辑距离
"""
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
"""
m = len(word1)
n = len(word2)
dp = [[0] * (n+1) for _ in range(m+1)]
for i in range(1, m+1):
dp[i][0] = i
for j in range(1, n+1):
dp[0][j] = j
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], dp[i][j-1], dp[i-1][j-1])+1
return dp[m][n]
技巧
(1) 水壶问题
"""
有两个水壶，容量分别为 x 和 y 升。水的供应是无限的。确定是否有可能使用这两个壶准确得到 target 升。你可以：
- 装满任意一个水壶
- 清空任意一个水壶
- 将水从一个水壶倒入另一个水壶，直到接水壶已满，或倒水壶已空。
"""
if x + y < target:
return False
def GCD(a, b):
if b == 0:
return a
return GCD(b, a % b)
return target % GCD(x, y) == 0
(2) 只出现一次的数字
"""
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
"""
res = 0
for num in nums:
res ^= num
return res
(3) 多数元素
"""
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
"""
counter = collections.Counter(nums)
return counter.most_common()[0][0]
# 摩尔投票
votes, count = 0, 0
for num in nums:
if votes == 0: x = num
votes += 1 if num == x else -1
for num in nums:
if num == x: count += 1
return x if count > len(nums) // 2 else 0
(4) 颜色分类
"""
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。必须在不使用库内置的 sort 函数的情况下解决这个问题。
"""
n = len(nums)
ptr = 0
for i in range(n):
if nums[i] == 0:
nums[i], nums[ptr] = nums[ptr], nums[i]
ptr += 1
for i in range(ptr, n):
if nums[i] == 1:
nums[i], nums[ptr] = nums[ptr], nums[i]
ptr += 1
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1: # 正好
mid += 1
else:
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1
(5) 下一个排列
"""
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
"""
i = len(nums) - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i >= 0:
j = len(nums) - 1
while j >= 0 and nums[i] >= nums[j]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
left, right = i + 1, len(nums) - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
(6) 寻找重复数
"""
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
"""
# 找到快慢指针相遇的点
slow = nums[0]
fast = nums[0]
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
# 找到环的入口点
slow = nums[0]
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow