多维动态规划（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 所使用的最少操作数。