动态规划（mid）

剑指 Offer II 096. 字符串交织

class Solution {
    
    public boolean isInterleave(String s1, String s2, String s3) {
    
        if (s1.length() + s2.length() != s3.length()) return false;
        int l1=s1.length();
        int l2=s2.length();
        boolean dp[][]=new boolean[l1+5][l2+5];
        dp[0][0]=true;
        for (int i = 1; i <= s1.length(); ++ i)
        {
       //当s2为空时，判断s1能否交织出s3
            dp[i][0] = s1.charAt(i-1) == s3.charAt(i-1)&& dp[i - 1][0];
        }

        for (int j = 1; j <= s2.length(); ++ j)
        {
       //当s1为空时，判断s2能否交织出s3
            dp[0][j] = s2.charAt(j-1) == s3.charAt(j-1) && dp[0][j - 1];
        }

        for(int i=1;i<=l1;i++){
    
            for(int j=1;j<=l2;j++){
    
                char ch1 = s1.charAt(i-1), ch2 = s2.charAt(j-1), ch3 = s3.charAt(i+j-1);
                dp[i][j]=(ch1==ch3&&dp[i-1][j])||(ch2==ch3&&dp[i][j-1]);
            }
        }
        return dp[l1][l2];
    }
}

剑指 Offer II 020. 回文子字符串的个数

class Solution {
    
public:
    int countSubstrings(string s) {
    
    int len = s.length();
    int dp[1000][1000];
    for(int i=0;i<len;i++){
    
        for(int j=0;j<len;j++) dp[i][j]=false;
    }
    int res = 0;
    for (int i = 0; i < len; i++) {
    
       for (int j = i; j >= 0; j--) {
    
         if (s[i] == s[j]) {
    
           if (i - j <= 1) {
    
             dp[i][j] = true;
           } else {
    
            dp[i][j] = dp[i - 1][j + 1];
           }
         }
          res += dp[i][j] ? 1 : 0;
        }
      }
         return res;
       }
};

剑指 Offer II 093. 最长斐波那契数列

class Solution {
    
    public int lenLongestFibSubseq(int[] arr) {
    
        int n = arr.length, res = 0;
        int[][] dp = new int[n][n];
        Map<Integer,Integer>mp=new HashMap<>();
        for(int i=0;i<n;i++)
            mp.put(arr[i],i);
        for(int i=1;i<n;i++){
    
            for(int j=0;j<i;j++){
    
                int tmp=arr[i]-arr[j];
                // 存在 k 使得 A[i] = A[j] + A[k] (0 <= k < j < i)
                if(mp.containsKey(tmp)&&mp.get(tmp)<j){
    
                    dp[i][j]=dp[j][mp.get(tmp)]+1;

                }
                // 存在 k 使得 A[i] = A[j] + A[k] (0 <= k < j < i)
                else dp[i][j]=2;
                res=Math.max(dp[i][j],res);
            }
        }
        return res>2?res:0; 
    }
}