一、
二、题目总结
2.1 回文子串个数647
（1）题目分析
子串，子数组是连续的，子序列是不连续的
DP[i][j] 表示子串i--j是否回文
状态转移方程为：
DP[i][j] = j-i<3 or DP[i+1][j-1], s[i]==s[j]
DP[i][j] = False, s[i]!=s[j]
解释：只要s[i]==s[j] && j-i<3，必然是回文，这里考虑了长度为2和3的情况。
（2）题解
def countSubstrings(s: str) -> int:
N = len(s)
if N == 0:
return 0
# 创建dp矩阵 (N,N), 事实上只使用了右上半部分
# dp[i][j] 表示子串i--j是否回文
dp_table = [[0 for _ in range(N)] for _ in range(N)]
# 初始化状态
# dp斜对角上 dp[0][0] dp[1][1]都是回文
res = 0 # 用来记录有多少个回文
for i in range(N):
dp_table[i][i] = True
res += 1
print(dp_table)
for j in range(1, N): # 1 2 3 ... N
for i in range(0, j): # 0 1 ... j
if s[i] == s[j]:
dp_table[i][j] = j-i <3 or dp_table[i+1][j-1]
else:
dp_table[i][j] = False
# dp_table[i][j] = s[i]==s[j] and (j-i <3 or dp_table[i+1][j-1])
if dp_table[i][j] == True:
res += 1
print(dp_table)
return res
test_case = "aaaa"
print(countSubstrings(test_case))
2.2 最大子数组之和 53
（1）题目分析
DP[i] 表示以i为结束位置的最大子数组之和
状态转移方程为：
DP[i] = max{ nums[i], nums[i]+dp[i-1]}, i>0
DP[i] = nums[i], i=0
（2）题解
from typing import List
def maxSubArray(nums: List[int]) -> int:
n = len(nums)
dp_table = [-float('inf') for _ in range(n)] # (N) matrix
dp_table[0] = nums[0]
res = nums[0]
for i in range(1, n):
dp_table[i] = max(nums[i], dp_table[i-1] + nums[i])
res = max(res, dp_table[i])
return res
nums = [-2,1,-3,4,-1,2,1,-5,4]
print(maxSubArray(nums))
2.3 最长回文子序列 516
（1）题目分析
子串，子数组是连续的，子序列是不连续的
DP[i][j] 表示子串i--j中最长回文子序列的长度
状态转移方程为：
DP[i][j] = 2 + DP[i+1][j-1], s[i]==s[j]
DP[i][j] = max{DP[i+1][j], DP[i][j-1]}, s[i]!=s[j]
（2）题解
def longestPalindromeSubseq(s: str) -> int:
N = len(s)
if N == 0:
return 0
# 创建dp矩阵 (N,N), 事实上只使用了右上半部分
# dp[i][j] 表示子串i--j是否回文
dp_table = [[0 for _ in range(N)] for _ in range(N)]
# 初始化状态
# dp斜对角上 dp[0][0] dp[1][1] 回文长度为1
for i in range(N):
dp_table[i][i] = 1
# print(dp_table)
for j in range(0, N): # 1 2 3 ... N
for i in range(0, j): # 0 1 ... j
if s[i] == s[j]:
dp_table[i][j] = 2 + dp_table[i+1][j-1]
else:
dp_table[i][j] = max(dp_table[i+1][j], dp_table[i][j-1])
#print(dp_table)
return dp_table[0][N-1]
test_case = "bbbab"
print(longestPalindromeSubseq(test_case))
2.4 最长公共子序列 1143
（1）题目分析
DP[i][j]表示text1[0..i]和text2[0..j]的最长子序列。DP[0][?]和DP[?][0]都为0
DP[i][j] = 1 + DP[i-1][j-1], text1[i]==text2[j]
DP[i][j] = max{ DP[i-1][j] , DP[i][j-1] }, text1[i]!=text2[j]
（2）题解
def longestCommonSubsequence(text1: str, text2: str) -> int:
n1 = len(text1)
n2 = len(text2)
if n1 == 0 or n2 == 0:
return 0
# 创建dp矩阵 (N,N), 事实上只使用了右上半部分
# dp[i][j] 表示子串i--j是否回文
dp_table = [[0 for _ in range(n2 + 1)] for _ in range(n1 + 1)] # 矩阵 (n1+1, n2+1)
# 初始化状态 dp_table第一行第一列都是0 dp_table[0][?]和dp_table[?][0]都为0
for j in range(1, n2 + 1): # 1 2 3 ... N
for i in range(1, n1 + 1): # 0 1 ... j
if text1[i-1] == text2[j-1]:
dp_table[i][j] = 1 + dp_table[i-1][j-1]
else:
dp_table[i][j] = max(dp_table[i-1][j], dp_table[i][j-1])
print(dp_table)
return dp_table[n1][n2]
t1 = "abcde"
t2 = "ace"
print(longestCommonSubsequence(t1, t2))
2.5 最短路径 62
（1）题目分析
DP[i][j]表示到达第i行第j类的路径数量
DP[i][j] = DP[i][j-1] + DP[i-1][j], i != 0 or j != 0
DP[i][j] = 1, *** i == 0 and j == 0***
（2）题解
def uniquePaths(m: int, n: int) -> int:
# m行n列
# dp[i][j] 表示到达第i行第j类的路径数量
dp_table = [[0 for _ in range(n)] for _ in range(m)] # 矩阵 (m, n)
# 初始化状态 dp_table第0行第0列都是1
for i in range(m):
dp_table[i][0] = 1
for j in range(n):
dp_table[0][j] = 1
# print(dp_table)
for i in range(1, m): # 1 2 3 ... m
for j in range(1, n): # 1 2 ... n
dp_table[i][j] = dp_table[i][j-1] + dp_table[i-1][j]
# print(dp_table)
return dp_table[m-1][n-1]
m = 3
n = 7
print(uniquePaths(m, n))
后记、模板总结
https://time.geekbang.org/column/article/297232
