再也不怕回文字符串的dp了

开发运维 2023-08-01 剑圣无痕 手机阅读

7.29面 tiktok测开一面
image.png

采用例题+自己理解的方式解决这个系列的问题

第一题：回文字符串的个数

image.png

递归五部曲：

  • 确定dp含义，dp[i][j]是i到j是否是回文字符串
  • 确定递推公式，

    • s.charAt(i)！=s.charAt(j)不用看了

    s.charAt(i)==s.charAt(j)：

    • "a","aa" 这一种长度小于2的肯定是的
    • "a???a" 这种只能看中间的是否是回文字符串了所以和f[i+1][j-1]有关
  • dp数组如何初始化 都是false f[i][i]的情况上面考虑到了
  • 递归顺序，根据地推公式，需要从左下往右上推，所以横排倒序，竖排正序
    image.png

    • 5.举例推导dp数组 6->2 9->4 10->5

    image.png

    class Solution {
    
    public int countSubstrings(String s) {
    
        int len = s.length();
    
        int ans = 0;
    

            boolean[][] f = new boolean[len][len];
    

            for(int i=len-1;i>=0;i--){
    
            for(int j = i;j=0;i--){
    
            for(int j=i;j