647. 回文子串
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
解题思路：
确认dp含义：dp[i][j] s[i:j]是否为回文串，是的话等于True，不是的话False
递推公式：如果s[i] == s[j]，三种情况：i == j，i-j=1, dp[i][j] = True, 如果i-j>1: dp[i][j] = dp[i-1][j-1]
初始化：dp[i][j] = False
遍历顺序：从下到上，从左到右
打印dp数组
class Solution:
def countSubstrings(self, s: str) -> int:
dp = [[0]*len(s) for _ in range(len(s))]
res = 0
for i in range(len(s)-1, -1, -1):
for j in range(i, len(s)):
if s[i] == s[j]:
if j-i<=1:
#only one or two index
dp[i][j] = 1
res += 1
else:
if dp[i+1][j-1] == 1:
dp[i][j] = 1
res += 1
return res 516.最长回文子序列
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
解题思路：
确认dp含义：dp[i][j]，s[i:j]中的最长回文子序列
递推公式：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])
初始化：当i==j,dp[i][j] = 1
遍历顺序：从下至上从左到右
打印dp数组:
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
dp = [[0]*len(s) for _ in range(len(s))]
for i in range(len(s)):
#initialize
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]:
#if same, dp[i+1][j-1]+2
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][len(s)-1]动态规划总结篇
代码随想录 (programmercarl.com)
动态规划基础
- 关于动态规划，你该了解这些！(opens new window)
- 动态规划：斐波那契数(opens new window)
- 动态规划：爬楼梯(opens new window)
- 动态规划：使用最小花费爬楼梯(opens new window)
- 动态规划：不同路径(opens new window)
- 动态规划：不同路径还不够，要有障碍！(opens new window)
- 动态规划：整数拆分，你要怎么拆？(opens new window)
- 动态规划：不同的二叉搜索树(opens new window)
#背包问题系列
- 动态规划：关于01背包问题，你该了解这些！(opens new window)
- 动态规划：关于01背包问题，你该了解这些！（滚动数组）(opens new window)
- 动态规划：分割等和子集可以用01背包！(opens new window)
- 动态规划：最后一块石头的重量 II(opens new window)
- 动态规划：目标和！(opens new window)
- 动态规划：一和零！(opens new window)
- 动态规划：关于完全背包，你该了解这些！(opens new window)
- 动态规划：给你一些零钱，你要怎么凑？(opens new window)
- 动态规划：Carl称它为排列总和！(opens new window)
- 动态规划：以前我没得选，现在我选择再爬一次！(opens new window)
- 动态规划： 给我个机会，我再兑换一次零钱(opens new window)
- 动态规划：一样的套路，再求一次完全平方数(opens new window)
- 动态规划：单词拆分(opens new window)
- 动态规划：关于多重背包，你该了解这些！(opens new window)
- 听说背包问题很难？ 这篇总结篇来拯救你了(opens new window)
#打家劫舍系列
- 动态规划：开始打家劫舍！(opens new window)
- 动态规划：继续打家劫舍！(opens new window)
- 动态规划：还要打家劫舍！(opens new window)
#股票系列
- 动态规划：买卖股票的最佳时机(opens new window)
- 动态规划：本周我们都讲了这些（系列六）(opens new window)
- 动态规划：买卖股票的最佳时机II(opens new window)
- 动态规划：买卖股票的最佳时机III(opens new window)
- 动态规划：买卖股票的最佳时机IV(opens new window)
- 动态规划：最佳买卖股票时机含冷冻期(opens new window)
- 动态规划：本周我们都讲了这些（系列七）(opens new window)
- 动态规划：买卖股票的最佳时机含手续费(opens new window)
- 动态规划：股票系列总结篇(opens new window)
#子序列系列
- 动态规划：最长递增子序列(opens new window)
- 动态规划：最长连续递增序列(opens new window)
- 动态规划：最长重复子数组(opens new window)
- 动态规划：最长公共子序列(opens new window)
- 动态规划：不相交的线(opens new window)
- 动态规划：最大子序和(opens new window)
- 动态规划：判断子序列(opens new window)
- 动态规划：不同的子序列(opens new window)
- 动态规划：两个字符串的删除操作(opens new window)
- 动态规划：编辑距离(opens new window)
- 为了绝杀编辑距离，我做了三步铺垫，你都知道么？(opens new window)
- 动态规划：回文子串(opens new window)
- 动态规划：最长回文子序列(opens new window)
#动规结束语（来源：代码随想录 (programmercarl.com)）
