小虾新近读一强人的博文时看到了记忆化搜索这个词，好奇之下，上网一番搜索，找了些资料来学习。记忆化搜索可以简要概括为“动态规划的原理，递归搜索的形式”。动态规划自底向上的推导过程，很多时候让小虾感觉不太容易处理和无所适从，所以觉得自顶向下的记忆化搜索更加平易近人，更加可爱。
新学的东西，需要通过实践来加强理解。所以，小虾找来了最长公共子串这个耳熟能详的题来实践。不同的是，以前多是在两个字符串上求LCS，即二维DP。试想，如果变成三个或者更多个的字符串上求LCS，自底向上的DP推导，应该会更加复杂。所以，小虾这里选择了三字符串求LCS来实践记忆化搜索。
int INTI = 1<<28; int[][][] dp; String str1, str2, str3; public int getLCS3(String str1, String str2, String str3) { this.str1 = str1; this.str2 = str2; this.str3 = str3; dp = new int[str1.length()][str2.length()][str3.length()]; for(int i=0; i<str1.length(); i++) for(int j=0; j<str2.length(); j++) Arrays.fill(dp[i][j], INTI); return go(str1.length()-1, str2.length()-1, str3.length()-1); } public int go(int i, int j, int k) { if(i<0||j<0||k<0) return 0; if(dp[i][j][k]!=INTI) return dp[i][j][k]; if(str1.charAt(i)==str2.charAt(j) && str1.charAt(i)==str3.charAt(k)) { dp[i][j][k] = go(i-1,j-1,k-1)+1; } else if(str1.charAt(i)==str2.charAt(j)) { int a = go(i-1,j-1,k); int b = go(i,j,k-1); dp[i][j][k] = Math.max(a, b); } else if(str1.charAt(i)==str3.charAt(k)) { int a = go(i-1,j,k-1); int b = go(i,j-1,k); dp[i][j][k] = Math.max(a, b); } else if(str2.charAt(j)==str3.charAt(k)) { int a = go(i,j-1,k-1); int b = go(i-1,j,k); dp[i][j][k] = Math.max(a, b); } else { int a = go(i-1,j,k); int b = go(i,j-1,k); int c = go(i,j,k-1); dp[i][j][k] = Math.max(a, Math.max(b, c)); } return dp[i][j][k]; }
