前言：最近准备笔试和面试的时候，发现了一个爱考的知识点——动态规划，特此整理。
1 最小路径和
力扣64题
题解
题目：给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
code：
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
if not grid or not grid[0]:
return 0
row, col = len(grid), len(grid[0])
dp = [[0] * col for _ in range(row)]
dp[0][0] = grid[0][0]
for i in range(1, row):
dp[i][0] = dp[i - 1][0] + grid[i][0]
for j in range(1, col):
dp[0][j] = dp[0][j - 1] + grid[0][j]
for i in range(1, row):
for j in range(1, col):
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
return dp[row - 1][col -1]
2 编辑距离
题目：给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：插入一个字符；删除一个字符；替换一个字符
code：
def minDistance(self, word1, word2):
n = len(word1)
m = len(word2)
# 有一个字符串为空串
if n * m == 0:
return n + m
# DP 数组
D = [ [0] * (m + 1) for _ in range(n + 1)]
# 边界状态初始化
for i in range(n + 1):
D[i][0] = i
for j in range(m + 1):
D[0][j] = j
# 计算所有 DP 值
for i in range(1, n + 1):
for j in range(1, m + 1):
left = D[i - 1][j] + 1
down = D[i][j - 1] + 1
left_down = D[i - 1][j - 1]
if word1[i - 1] != word2[j - 1]:
left_down += 1
D[i][j] = min(left, down, left_down)
return D[n][m]
3 最长回文子序列
力扣516题
题解
题目：给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
code：
def longestPalindromeSubseq(self, s):
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
dp[i][i] = 1
for j in range(i + 1, n):
if s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
return dp[0][n - 1]
4 两个字符串的删除操作
力扣583题
题解
题目：给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。
code:
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
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] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
max_sub = dp[m][n]
return m - max_sub + n - max_sub
5 最长公共子序列
力扣1143题
题解
题目：给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在 公共子序列，返回 0 。
code：
def longestCommonSubsequence(self, text1, text2):
"""
:type text1: str
:type text2: str
:rtype: int
"""
m, n = len(text1), 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]
6 让字符串成为回文串的最少插入次数
力扣1312题
题解
题目：给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
请你返回让 s 成为回文串的最少操作次数 。
code：
def minInsertions(self, s):
n = len(s)
t = s[::-1]
dp = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, n + 1):
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
if s[i - 1] == t[j - 1]:
dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1)
return n - dp[n][n]