剑指 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
for(int j=0;j
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];
Mapmp=new HashMap<>();
for(int i=0;i
for(int j=0;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)
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;
}
}