动态规划之回文串两个数组的dp问题

目录回文串问题回文子串的dp表示最长回文子串两个数组的dp问题最长公共子序列初始化技巧编辑距离初始化注意事项回文串问题回文子串最长回文子串弄清楚回文子串问题就可以弄清最长回文子串问题。回文子串的dp表示注意事项初始化顺序是从前往后从下往上注意ij故只取dp表的一半class Solution { public int countSubstrings(String s) { int ns.length(); boolean[][] fnew boolean[n][n]; f[0][0]true; int count0; for(int in-1;i0;i--){ for(int ji;jn-1;j){ if(s.charAt(i)!s.charAt(j)){ f[i][j]false; }else{ if(ij){ f[i][j]true; count; }else if(i1j){ f[i][j]true; count; }else{ f[i][j]f[i1][j-1]; if(f[i][j]true){ count; } } } } } return count; } }最长回文子串class Solution { public String longestPalindrome(String s) { int ns.length(); boolean[][] fnew boolean[n][n]; f[0][0]true; for(int in-1;i0;i--){ for(int ji;jn-1;j){ if(s.charAt(i)!s.charAt(j)){ f[i][j]false; }else{ if(ij){ f[i][j]true; }else if(i1j){ f[i][j]true; }else{ f[i][j]f[i1][j-1]; } } } } //走到这里 统计f表每行 为true的距离相差的最大 int max0; int begin0; for(int i0;in-1;i){ for(int ji;jn-1;j){ if(f[i][j](j-i1)max){ maxj-i1; begini; } } } return s.substring(begin,beginmax); } }两个数组的dp问题最长公共子序列编辑距离最长公共子序列初始化技巧class Solution { public int longestCommonSubsequence(String s1, String s2) { int ms1.length(); int ns2.length(); int[][] fnew int[m1][n1]; s1 s1; s2 s2; int max0; for(int i1;im;i){ for(int j1;jn;j){ if(s1.charAt(i)s2.charAt(j)){ f[i][j]f[i-1][j-1]1; maxMath.max(f[i][j],max); }else{ f[i][j]Math.max(f[i][j-1],f[i-1][j]); maxMath.max(f[i][j],max); } } } return max; } }编辑距离初始化注意事项注意初始化的值技巧都是同最长公共子序列的class Solution { public int minDistance(String s1, String s2) { int ms1.length(); int ns2.length(); int[][] fnew int[m1][n1]; //初始化 for(int j0;jn;j){ f[0][j]j; } for(int i0;im;i){ f[i][0]i; } s1 s1; s2 s2; for(int i1;im;i){ for(int j1;jn;j){ if(s1.charAt(i)s2.charAt(j)){ f[i][j]f[i-1][j-1]; }else{ f[i][j]Math.min(f[i-1][j-1]1,Math.min(f[i][j-1]1,f[i-1][j]1)); } } } return f[m][n]; } }