115. 不同的子序列

115. 不同的子序列

题目描述：

给定一个字符串 s 和一个字符串 t，计算在 s 的子序列中 t 出现的个数。

dp五部曲：

1. dpi 表示 s下标在[0,i-1]中与 t下标在[0,j-1]中不同子序列的个数

int dp = new intm + 1;

1. 递推公式：（两类情况）

if (s.charAt(i - 1) == t.charAt(j - 1)) // 匹配

这第一类又分为两小种情况：

由于不用连续，所以，计算当前位置匹配，仍然可以选择不使用当前元素；即，dpi - 1;

如果使用当前元素进行匹配，则 dpi - 1 第一大类情况是这两小种情况之和

即，dpi = dpi - 1 + dpi - 1;

if (s.charAt(i - 1) == t.charAt(j - 1)) // 不匹配，则删除s[i-1]

dpi = dpi - 1;

1. 初始化

dpi 表示删除s[i]后是空串的个数，所以全是1 dp0 表示删除空串s后是t[j-1]的个数，不可能，所以全是0

1. 顺序：从左到右
2. 打印dp

516. 最长回文子序列

题目描述：

给定一个字符串 s，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000。

子串连续，但是子序列可以不连续

dp 五步曲：

1. dp[i] 表示：如果子串[i,j]范围内最长回文串的长度

int dp = new int[n];

1. 递推公式

if (s.charAt(i) == s.charAt(j)) { // 首尾匹配

dp[i] = dp[i] + 1 + 2;

if (s.charAt(i) != s.charAt(j)) { // 首尾不匹配

首尾字符不匹配，则 [i,j]子串一定不是回文串，则需要看[i+1,j]和[i,j-1]中的max回文串 dp[i] = Math.max(dp[i] + 1, dp[i]);