5.最长回文串
5. 最长回文子串
https://leetcode.cn/problems/longest-palindromic-substring/
先全部置为false然后反向遍历。动态规划数组，dp【i】【j】表示从第i到第j 是否是回文串。Arrays.fill表示的是将指定的内容填充到数组中。状态转移方程如下
这个题目用到了charAt索引处，所以就不必要去索引对齐，因为你索引对齐了以后，使用charAt的时候还是要+-1还是很麻烦
charAt：从字符串中取第几个数
Arrays.fill:批量填充
substring：取子集
class Solution {public String longestPalindrome(String s) {int m = s.length();boolean[][] dp = new boolean[m][m];int res = 0;String str = "";for(int i = 0; i < m; ++i){Arrays.fill(dp[i],false);} for(int i = m - 1 ; i >= 0; i--){for(int j = i; j < m; ++j){if(s.charAt(i) == s.charAt(j) &&(j - i <= 1 || dp[i + 1][j - 1])){dp[i][j] = true;res = Math.max(res,j - i + 1);if(j - i + 1>= res){str = s.substring(i, j +1);}}}}return str;}
}139.单词拆分
139. 单词拆分https://leetcode.cn/problems/word-break/这里的状态转移方程就是下式，check检查是否出现。首先创建了一个哈希表取排除了这个相同的元素，HashSet不保证元素的顺序，并且不允许null元素。
其次需要注意是，创建哈希表时范围+1来保证索引对齐 ，dp【i】表示的就是第i个数字之前能由拆分的单词组成。边界条件是dp【0】 =true表示空串并且合法，这里要注意substring函数的使用表示的是取从第i个字符到第j - 1 个字符子串。
contains方法：个集合或数组中是否包含特定的元素
class Solution {public boolean wordBreak(String s, List<String> wordDict) {Set<String> wordDictSet = new HashSet(wordDict);boolean []dp = new boolean[s.length() + 1];//为了索引对齐(下一行)dp[0] = true;for(int i = 1; i <= s.length(); ++i){for(int j = 0; j < i; ++j){if(dp[j] && wordDictSet.contains(s.substring(j ,i))){dp[i] = true;break;}}}return dp[s.length()];}
}516.最长回文子序列
516. 最长回文子序列https://leetcode.cn/problems/longest-palindromic-subsequence/
用 dp[i][j] 表示字符串 s 的下标范围 [i,j] 内的最长回文子序列的长度。假设字符串 s 的长度为 n，则只有当 0≤i≤j<n 时，才会有 dp[i][j]>0，否则 dp[i][j]=0。
边界：由于任何长度为 1 的子序列都是回文子序列，因此动态规划的边界情况是，对任意 0≤i<n，都有 dp[i][i]=1。
（1） s[i]=s[j] dp[i][j]=dp[i+1][j−1]+2；
（2） s[i]!=s[j] dp[i][j]=max(dp[i+1][j],dp[i][j−1])。
class Solution {public int longestPalindromeSubseq(String s) {int n = s.length();int dp[][] = new int [n][n];for(int i = n - 1; i >= 0; --i){dp[i][i] = 1;char c1 = s.charAt(i);for(int j = i + 1; j < n; ++j){char c2 = s.charAt(j);if(c1 == c2){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];}
}712.两个字符串的最小ASCII删除和
712. 两个字符串的最小ASCII删除和https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/ dp[i][j] 表示使 s1[0:i] 和 s2[0:j] 相同的最小 ASCII 删除和
i = j = 0时，都为空不需要删除，dp[0][0] = 0，当i=0，j>0或i>0，j=0的时候，如果要相同，就需要删除全部的字符
这里codePointAt函数是取ASCII
当 i>0 且 j>0 时，考虑 dp[i][j] 的计算，
要得到使 s 1[0:i] 和 s 2[0:j] 相同的最小 ASCII 删除和，应取两项中较小的一项
class Solution {public int minimumDeleteSum(String s1, String s2) {int m = s1.length();int n = s2.length();int dp[][] = new int [m + 1][n + 1];for(int i = 1; i <= m; ++i){dp[i][0] = dp[i - 1][0] + s1.codePointAt(i - 1);//只考虑s1的前i -1个字符删除s1中的字符和s2匹配}for(int j = 1; j <= n; ++j){dp[0][j] = dp[0][j - 1] + s2.codePointAt(j - 1);}for(int i = 1; i <= m; ++i){int c1 = s1.codePointAt(i - 1);for(int j = 1; j <= n; ++j){int c2 = s2.codePointAt(j - 1);if(c1 == c2){dp[i][j] = dp[i - 1][j - 1];}else{dp[i][j] = Math.min(dp[i - 1][j] + c1,dp[i][j - 1] + c2);}}}return dp[m][n];}
}115.不同的子序列
115. 不同的子序列https://leetcode.cn/problems/distinct-subsequences/dp的 hard题目，稍微难想，套路相似，定义dp的含义是s和t两个字符串dp[i][j]表示的是t字符串从索引为j到最后末尾这个字串是否是s字符串索引为i的字串的子集。
考虑动态规划的边界情况，就是j = n的时候，t字符串是空集，空集是任何字符串的子集，所以对于任意0≤i≤m，有 dp[i][n]=1；
当 i=m 且 j<n 时，s[i:] 为空字符串，t[j:] 为非空字符串，由于非空字符串不是空字符串的子序列，因此对任意 0≤j<n，有 dp[m][j]=0。
当 i<m 且 j<n 时，考虑 dp[i][j] 的计算：
当 s[i]=t[j] 时，dp[i][j] 由两部分组成：
这里涉及一个匹配和不匹配的问题，就是说，当s[i]=t[j] ，s[i]可以去匹配t[j]的这个字符也可以不匹配，当不相等的时候就一定不匹配
class Solution {public int numDistinct(String s, String t) {int m = s.length();int n = t.length();if(m < n){return 0;}int [][] dp = new int[m + 1][n + 1];for(int i = 1; i <= m; ++i){dp[i][n] = 1;}for(int i = m - 1; i >= 0; i--){char c1 = s.charAt(i);for(int j = n - 1; j >= 0;j--){char c2 = t.charAt(j);if(c1 == c2){dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j];}else{dp[i][j] = dp[i + 1][j];}}}return dp[0][0];}
}
