Topic describes

Given a string s, find the longest substring in s.

Their thinking

This is an entry level dynamic programming algorithm that uses j to represent the starting position of a substring, and I to represent the ending position of a substring. A substring is a subroutine, and dp[I][j] is a subroutine. Write a dynamic programming equation dp [I] [j] = dp [I + 1] [1] && s.c harAt [I] = = s.c harAt [j].

AC code

class Solution { public String longestPalindrome(String s) { int len=s.length(); boolean[][] dp=new boolean[len][len]; int max=1; int start=0; for(int i=0; i<len; i++){ for(int j=0; j<=i; j++){ if(i-j==0){ dp[i][j]=true; }else if(i-j==1){ dp[i][j]=s.charAt(i)==s.charAt(j); }else{ dp[i][j]=dp[i-1][j+1]&&s.charAt(i)==s.charAt(j); } if(dp[i][j]&&i-j+1>max){ max=i-j+1; start=j; } } } return s.substring(start,start+max); }}Copy the code

conclusion

In this kind of dynamic programming, the devil is in the details. First of all, I didn’t pick Max 1, I couldn’t get the position of I and j wrong, and finally the value of j is 0<j<= I