算法学习：动态规划2-字符串与子序列问题
一般关于字符串的都是二维dp
1 最大回文子串
1.1 递归关系
设置dp[i][j]是以索引i开头索引j结尾的字符串是否为回文串
此种遍历由下到上开始遍历
1.2 边界条件
串长度为1，都是回文串
子串长度为2
1.3 代码
class Solution {
public String longestPalindrome(String s) {
//与字符串的一般都是二维
/**
设置dp[i][j]是以索引i开头索引j结尾的字符串是否为回文串
dp[i][j] = dp[i+1][j-1]&&s[i]==s[j]
初始 dp[i][i] = 1, dp[i][i+1] = s[i]==s[i+1]
*/
int len = s.length();
boolean[][]dp = new boolean[len][len];
int start = 0;
int end = 0;
//初始化
for(int i = 0;i<len;i++){
dp[i][i] = true;
start = i;
end = i+1;
}
for(int i = 0;i<len-1;i++){
dp[i][i+1] = s.charAt(i)==s.charAt(i+1);
if(dp[i][i+1]){
start = i;
end = i+2;
}
}
//从下到上遍历
for(int i = len-3;i>=0;i--){
for(int j = i+2;j<len;j++){
dp[i][j] = dp[i+1][j-1]&&s.charAt(i)==s.charAt(j);
if(dp[i][j]){
if(j+1-i>end-start){
start = i;
end = j+1;
}
}
}
}
return s.substring(start,end);
}
}
2 最长回文子序列
2.1 递归关系
2.2 边界条件
起始的
2.3 代码
class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[][]dp = new int[n][n];
for(int i =0;i<n;i++){
dp[i][i] = 1;
}
//倒着遍历
for(int i = n-2;i>=0;i--){
for(int j = i+1;j<n;j++){
if(s.charAt(i)==s.charAt(j)){
dp[i][j] = dp[i+1][j-1]+2;
}else{
dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
}
}
}
return dp[0][n-1];
}
}
3 单词拆分（一维dp）
3.1 递归关系
首先弄一个集合set，存储字符串列表中的所有字符串，然后开辟一维dp数组，其中dp[i]的意思代表s[0,i-1]的子串是否能被列表集合单词拆分。二维遍历dp数组
只要遍历中有一次为true立马结束循环
3.2 边界条件
起始的dp[0]为true
3.3 代码
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
boolean[]dp = new boolean[s.length()+1];
Set<String>set = new HashSet<>(wordDict);
dp[0] = true;
for(int i = 1;i<s.length()+1;i++){
for(int j = 0;j<i;j++){
dp[i] = dp[j]&&set.contains(s.substring(j,i));
if(dp[i]==true){
break;
}
}
}
return dp[s.length()];
}
}
4 编辑距离
4.1 递归关系
4.2 边界条件
需要注意的是在申请dp数组的时候多申请一行一列，存放空串，空串到任意串的步数都是任意串的长度
4.3 代码
class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
int[][]dp = new int[m+1][n+1];
//初始化边界
for(int i = 0;i<m+1;i++){
dp[i][0] = i;
}
for(int i = 0;i<n+1;i++){
dp[0][i] = i;
}
//递归
for(int i = 1;i<m+1;i++){
for(int j = 1;j<n+1;j++){
//注意这里的i-1，j-1
if(word1.charAt(i-1)==word2.charAt(j-1)){
dp[i][j]=dp[i-1][j-1];
}else{
dp[i][j] = Math.min(
Math.min(dp[i-1][j],dp[i][j-1]),
dp[i-1][j-1])
+1;
}
}
}
return dp[m][n];
}
}
5 最长递增子序列
5.1 递归关系
双重循环，dp[i]代表到以nums[i]结尾的最长子序列的长度，设定第二个变量j，j由0->i，每次如果nums[i]>nums[j]，那么dp[i]刷新为max(dp[j]+1)，最后取dp的最大值
5.2 边界条件
起始初始化所有的dp[i] = 1
5.3 代码
class Solution {
public int lengthOfLIS(int[] nums) {
int len = nums.length;
int[]dp = new int[len];
Arrays.fill(dp,1);
int ans = 1;
for(int i = 1;i<len;i++){
for(int j = 0 ;j<i;j++){
if(nums[i]>nums[j]){
dp[i] = Math.max(dp[i],dp[j]+1);
ans = Math.max(ans,dp[i]);
}
}
}
return ans;
}
}
5.4 最长递增子序列的个数
- 多使用一个cnt数组记录当前nums[i]结尾的最长地址子序列的个数
- 如果dp[j]+1>dp[i]，代表当前的最长子序列更新了，那么cnt[i] = cnt[j]，为前一个
- 如果dp[j]+1==dp[i]，那么最长子序列的个数又得更新，cnt[i]+=cnt[j]
- 最后取dp[i]最大值对应的cnt数值即可
class Solution {
public int findNumberOfLIS(int[] nums) {
int len = nums.length;
int[]dp = new int[len];
int[]cnt = new int[len];
Arrays.fill(dp,1);
Arrays.fill(cnt,1);
int ans = 1;
for(int i = 1;i<len;i++){
for(int j = 0 ;j<i;j++){
if(nums[i]>nums[j]){
if(dp[j]+1>dp[i]){
//找到了更长的,那边数字不变
cnt[i] = cnt[j];
}else if(dp[j]+1==dp[i]){
//又一样长的，加上
cnt[i] += cnt[j];
}
dp[i] = Math.max(dp[i],dp[j]+1);
}
}
ans = Math.max(ans,dp[i]);
}
//然后找出cnt中为ans的统计
int res = 0;
for(int i = 0;i<len;i++){
if(dp[i]==ans){
res += cnt[i];
}
}
return res;
}
}