代码随想录算法训练营 Day 40
Published:
动态规划五部曲
- 确定dp数组以及下标的含义
- 确定递推公式
- 初始化dp数组
- 确定遍历顺序
- 举例推导dp数组
第5步随着输入不同而变化，因此在此省去
Q1. LeetCode 647
class Solution:
def countSubstrings(self, s: str) -> int:
n = len(s)
dp = [[0] * n for _ in range(n)]
res = 0
for i in range(n - 1, -1, -1):
for j in range(i, n):
if s[i] == s[j]:
if j - i <= 1:
res += 1
dp[i][j] = 1
elif dp[i + 1][j - 1]:
res += 1
dp[i][j] = 1
return res
复杂度分析
时间复杂度：O($n^2$) 空间复杂度：O($n^2$)
Q2. LeetCode 516
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
dp = [[0] * len(s) for _ in range(len(s))]
for i in range(len(s)):
dp[i][i] = 1
for i in range(len(s) - 1, -1, -1):
for j in range(i + 1, len(s)):
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][-1]
复杂度分析
时间复杂度：O($n^2$) 空间复杂度：O($n^2$)